浅谈两种nim游戏

1. 啥是标准nim游戏？

   题目来源洛谷

   有$n$堆石子，每堆有$a_i$个石子。

   每人每次可以在一堆石子中取一些石子扔掉，，可以取完，不能不取。每次只能从一堆里取。

   最后没石子可取的人就输了。假如甲是先手，且告诉你这$n$堆石子的数量，他想知道是否存在先手必胜的策略。

   这个策略就是nim游戏。

2. nim游戏怎么做到先手必败？

若$a_1\oplus a_2\oplus ...a_n=0$，那么甲输。

否则乙输。

3. 代码？（多组数据）

   时间复杂度$O(tn)$

    #include<bits/stdc++.h>
    #define ns "-1"
    #define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
    #define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
    #define ll long long
    #define ull unsigned long long
    #define db double
    #define ms(a,b) memset(a,b,sizeof(a))
    #define sz(a) sizeof(a)
    using namespace std;
    const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
    const int N=100001,inf=0x7f7f7f7f;
    int n,a,m,jk;
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin>>n;
        fs(i,1,n,1){
            cin>>m;jk=0;
            fs(i,1,m,1){
                cin>>a;
                jk^=a;
            }
            if(jk==0) cout<<"No\n";
            else cout<<"Yes\n";
        }
        return 0;
    }
   
   

4. 第一种扩展nim游戏

来源AcWing

现在，有一个$n$级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有$a_i$个石子($i\ge 1$)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

5. 第一种扩展题解

如果如果先手时奇数台阶上的值的异或值为$0$，则先手必败，反之必胜。

也就是说，若$n$是奇数，那么若$a_1\oplus a_3\oplus ...a_n=0$，那么甲输。

否则若$a_1\oplus a_3\oplus ...a_{n-1}=0$，那么甲输。

6. 代码

    #include <iostream>
    using namespace std;
    int res,a,n;
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a;
            if(i&1) res^=a;
        }
        if(!res) puts("No");
        else puts("Yes");
        return 0;
    }//AcWing上有时间限制提交，所以代码比较丑