ACM/ICPC 2011 成都现场赛 Alice and Bob 题解

这种博弈问题我做得很少，开始在纸上推，还是比较复杂。看了别人的题解才大概知道应该怎么做。大体上是把问题等价地简化，然后就有点类似动态规划了：先把边界搞清楚，然后记忆化递归看是必胜还是必败。

从这道题的规则上看，每次操作要么让一组数减 1, 要么把两组数合并成一组。其实还有一个特别的地方，那就是，如果有某组数是 1, 如果有一方让这组数减 1, 这组数就被抹掉了，组数同时也少了 1. 所以如果有一组数是 1 的话，将其减 1 的操作，相当于平时操作了两下，就改变了奇偶性。

我们可以发现，如果玩家面临的局面，剩下的可行操作次数是偶数次，那么他必败。如果有 n 组数，并且每组都大于 1, 必胜的玩家可以保证可行操作的奇偶性不改变，因为对方没有办法遇到某组数为 1（只有这样才能改变奇偶性）。但是如果有若干组的数字是 1, 那就复杂了。

所以状态的描述 dp[i][j] 表示，有 i 组的数字是 1, 且其它组（即数字不为 1 的组）的“可操作数”为 j 的时候，先手是必胜还是必败。其中“可操作数”的计算：当没有其它数字的组的时候，可操作数为 0; 当只有一个组时，可操作数为那个组的数字；当有 n > 1 个组时，可操作数为 (S + n – 1), 其中 S 是那些组的数字之和。

状态转移过程中的重点，是把两个为 1 的组合并的时候，会产生一个大于 1 的组。这会根据“可操作数”的不同而产生两种情况，具体在代码的 33 到 39 行找。