（蓝桥真题）异或数列（博弈）

题目链接：P8743 [蓝桥杯 2021 省 A] 异或数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例输入：

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

样例输出：

1
0
1
1

分析：容易想到对于异或最大值的问题肯定是按位来进行考虑，优先考虑权值比较高的位，假如我们当前考虑第pos位（那么就是前pos位并没有分出胜负），不妨假设有x个数该位为1，那么就有n-x个数该位为0.

假如x是偶数，那么显然在该位上是分不出胜负的，因为如果要是Alice有t个数该位为1，那么无论怎样分，t和x-t奇偶性都相同，那么异或起来值是相同的

假如x是奇数，那么显然在该位一定可以分出胜负，因为无论怎样分，最后都只有一个人可以在该位为1.

在这种情况下还需要分情况讨论：

如果x=1，那么显然Alice首次操作会直接选该位为1的数，那么Alice直接获胜

如果x!=1，那么也就是说x是一个大于1的奇数，这个时候如果该位为0的个数n-x是偶数那么先手获胜，否则先手必败。先来说一下先手必胜的操作方法，先手先取一个该位为1的数，接下来该位为1的数和为0的数剩余的个数都是偶数个，那么先手只需要跟随后手的操作即可，也就是说假如后手选一个该位为1的数操作自己，那么先手就选一个该位为1的数操作后手，这样后手在该位始终为0，同理可分析其他类似操作，这样先手必胜。那么下面说一下如果n-x是奇数时先手必败的原因，假如先手先选取一个该位为1的数操作自己，那么后手就选择一个该位为0的数操作自己，这个时候该位为1的数和为0的数都变为了偶数个，接下来如果先手选择该位为0的数操作，那么后手也选择该位为0的数操作，这样可以维持该位为0的数的个数一直是偶数，如果先手选择该位为1的数操作自己，那么先手该位就会为0，那么这个时候后手选取该位为1的数操作自己，那么后手在该位上就会为1，在此之后无论先手怎么操作，后手总能使得后手该位为1，先手该位为0，这个是很好分析的。如果先手选择该位为1的数操作后手，那么后手该位就变为了1，那么同理后手可选择该位为1的数操作先手，这个时候也能到达后手该位为1，先手该位为0的状态，接下来就跟上面一样，后手总能使得后手该位为1，先手该位为0，那么后手必胜！如果先手先选取一个该位为0的数操作自己，那么相对于后手的局面就变为先手操作，而且该位为1的个数为奇数，且为0的个数为偶数，所以是必胜局面。综上所述，对于该局面，后手必胜！

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
int num[31];
int Log2[1<<22];
int lowbit(int x)
{return x&-x;
}
int main()
{int T,n;for(int i=0;i<=20;i++)Log2[1<<i]=i;cin>>T;while(T--){scanf("%d",&n);for(int i=20;i>=0;i--)num[i]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);while(a[i]){num[Log2[lowbit(a[i])]]++;a[i]-=lowbit(a[i]);}}bool flag=false;for(int i=20;i>=0;i--)if(num[i]&1){flag=true;if(num[i]==1)puts("1");else if(n&1)//该位为1的个数大于1且为0的个数是偶数 puts("1");elseputs("-1");//该位为1的个数大于1且为0的个数是奇数break;}if(!flag) puts("0");}return 0;
}