Nim游戏中的状态

先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0

结论

假设n堆石头，石头的数量分别是a1，a2，a3……an。如果a1^a2^a3……^an ≠ 0，先手必胜；否则先手必败

证明与解释

  1. 这场游戏的终态是 0^0^0^0^0^……^0 = 0
  2. 在操作过程中，如果 a1^a2^a3……^an ≠ 0,那么下一个玩家必定可以通过拿一个或者多个石头使得结果变成0.
  3. 所以如果先手遇到a1^a2^a3……^an = 0的局面,双方都进行最优解操作，无论先手怎么最终都会是后手让等式=0，从而导致先手必败状态。

证明（NIM博弈）

image

Nim游戏题目描述

给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

代码

#include <iostream>
using namespace std;

int main()
{
    int n;
    int res = 0;
    cin >> n;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        res ^= x;
    }
    if(res != 0)puts("Yes");
    else puts("No");
    return 0;
}