大家好,我是吴师兄。

无论是 Dota、LOL 还是其它 MOBA 游戏,比赛中均存在着 Ban Pick 机制:参与比赛的双方队伍通过数轮禁用/选取英雄后,最终确定游戏比赛的英雄阵容

这是一个斗智斗勇的环节,布置陷阱、各种套路与反制让很多没有玩过游戏的小伙伴也能享受电竞的魅力。

Ban Pick 就是为了能给对战双方创造出一个平等的对战环境,因为如果没有这个环节,那么就变成了投硬币游戏,先手的一方具有极大的优势,可以选择版本强势英雄。

就像五子棋,如果是不带禁手的规则,那么先手黑棋必胜,1992 年 Victor Allis 通过编程证明这一点,感兴趣的小伙伴也可以自己编程尝试证明。

在 LeetCode 里面也存在着这样一道题目,先手必胜,这道题目是 LeetCode 第 877 号问题 石子游戏

依旧先给没有见过这道题目的小伙伴补充一下前置知识,石子游戏 讲的是你和小伙伴两个人用几堆石子玩游戏,一共有偶数堆石子,排成一行;每堆都有正整数颗石子,数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负,由于石子的总数是奇数,所以不存在平局

接下来,两个人轮流开始选择,假设你先手每回合你们都可以从行的开始或结束处取走整堆石头,直到没有更多的石子堆为止,此时手中石子最多的玩家获胜

举个例子:

一开始,你只能选择拿前 5 颗或后 5 颗石子,假设你选择拿前 5 颗,那么就剩下的这一行石子就变成了这种样子。

如果你的对手选择拿走前 3 颗,那么剩下的是 [4,5],你拿走后 5 颗赢得 10 分,大于了对手的 3 + 4 = 7

如果你的对手选择拿走后 5 颗,那么剩下的是 [3,4],你拿走后 4 颗赢得 9 分,,大于了对手的 5 + 3 = 8

对于 [5,3,4,5] ,先手的你可以赢得比赛

题目让我们去判断一下,给定任意一个数组,假设你和对手都能发挥最佳水平,并且是你先手,最终赢得游戏的人是谁?

这道题目和我们昨天分析的 LeetCode 第 292 号问题 Nim 游戏 一样,是可以采取动态规划的思路来思考的,这里我就不展开讲了。

这道题目同样是一道博弈论的问题,答案只有一行代码,先手必胜

class Solution {
    public boolean stoneGame(int[] piles) {
        // 先手必胜
        return true;
    }
}

详细分析一下。

由于石子的堆数为偶数,那么肯定是可以划分为同样堆数的两个集合,奇数堆集合与偶数堆集合。

1、青色的序列都是奇数,是奇数堆集合。

2、绿色的序列都是偶数,是偶数堆集合。

再次注意,由于石子的堆数为偶数,那么一开始最左边的石子堆必然是奇数堆,最右边的石子堆必然是偶数堆。

每次在你选完对手再选完后,完成了一个回合,剩下的石子堆的堆数依旧是偶数。

这也就意味着,如果你选择了奇数序列开局,那么你总可以把所有的奇数序列都选取。

比如,你选择了 1 号,如果对手选择 6 号,你可以选择奇数序列 5 号;如果对手选择 2 号,你可以选择奇数序列 3 号;

那么,如果奇数序列的所有石子总数大于了偶数序列的所有石子总数,那么你就可以赢得游戏。

同样的,如果偶数序列的所有石子总数大于了奇数序列的所有石子总数,那么你可以采取先选偶数序列,然后每一次都选偶数序列的方式,最终总可以把所有的偶数序列都选取,从而赢得游戏。

所以先手必胜!

回到标题,为什么在 Dota2 第十届国际邀请赛的决赛夜中,LGD 在两局落后的情况下连扳两局,有望创造让二追三的奇迹时,却选择在决胜局中不 ban 版本强势英雄猛犸,让对方先手抢到了,最终不敌 TS。

排除了大家能猜想的一切可能,只剩下一个可能:他们没有刷 LeetCode !

所以,我给他们微博发了一条私信,希望今年的比赛他们不要再犯这种低级错误了。