台阶-Nim游戏

• 核心思想：博弈论

  • 可以看作第i阶台阶上有i个含有i个石子的堆
  • 这样所有台阶上一共n!个堆就变成了经典Nim
  • 优化：发现偶数阶台阶上2n堆异或 = 0 , 奇数阶台阶异或 = 原本石子数量
    • 因此 当遍历到奇数阶时异或一下就行

    •   #include 
        #include 
        
        using namespace std;
        
        const int N = 100010;
        
        int main()
        {
            int n;
            scanf("%d", &n);
        
            int res = 0;
            for (int i = 1; i <= n; i ++ )
            {
                int x;
                scanf("%d", &x);
                if (i & 1) res ^= x;
            }
        
            if (res) puts("Yes");
            else puts("No");
        
            return 0;
        }