博弈论

尼姆(nim)游戏:

P2197 【模板】Nim 游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于博弈论游戏,如果当前的选手具有控制权的话,那么当前选手是必赢的,也就是当前选手做出的这步选择后,之后的局面都是在其预料之中的,换句话说,先掌握了控制权即赢. 考虑什么情况下是控制权,对于一个局面,我们最终的局面一定是 0 0 0 0....,其异或和为 $0$.

那么存在定义异或和为0 的局面为局面 $0$,其余局面为局面 $1$,若当前局面为 $0$ 局面,那么下一步一定会变成 $1$ 局面, 若当前局面为 $1$ 局面,那么当前局面可根据选手选择变成 $0$ 或者 $1$即当前局面为选手掌握控制权局面,则胜出

故: 若一开始的局面为 $0$ 局面那么后手一定掌握控制权,即后手赢,否则先手赢

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,res; cin>>n>>res;
    for(int i=2;i<=n;i++){
        int x; cin>>x;
        res^=x;
    }
    if(res) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
signed main(){
    int t; cin>>t; while(t--) solve();
}