原题链接

为了能够找出该Nim游戏的必胜方法，应该从最基本的样例中找到规律：

  1. 如果石子都在第一层，那我全部拿下去就获胜了。
  2. 如果石子全部在偶数层，对手拿下来多少个石子，我就把这石子都移到下面一层，这样保证我最后把所有石子都放在了最底下。这说明了偶数层并不会对胜负有影响。
  3. 终结情况是全0
  4. 伴随着每一次移动，会有相邻两个台阶的石子数发生变化。一个变大，一个变小。

私以为Nim游戏最难理解的地方就在于为什么要使用异或，但是异或是最简练也是最为准确地能够描述每次状态变化地结果量。
我们可以猜测，是奇数台阶异或为0时是必胜情况。
那么怎么进行证明呢？可以这么去理解。当奇数台阶结果异或为0时，下一次操作时候异或结果肯定不为0，下下次的结果肯定又能回到0。由于石子的数目肯定是逐渐变少的，因此这个结果肯定会归到0，必胜结果一定为0。

结论

计算奇数台阶石子的异或，异或为0说明必胜。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    int res = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        if(i % 2 == 0) res ^= a;
    }
    if(res) printf("Yes");
    else printf("No");
    return 0;
}