游戏结束后,所有数都全部取完,并且异或到了a或b上,所以:
sum=x1^x2^…^xn=a^b
如果sum=0,说明a=b,则游戏平局
如果sum!=0,不妨取sum的最高一位1(假设在第k位),a和b中必然有一个第k位取1,一个第k位取0,所以,谁第k位取1则数大,获胜。
故我们只需要考虑所有xi的第k位即可,这样就从n个数的问题变成了n个0或1的问题
设x个奇数,y个偶数,由于最终异或结果是1,所以x一定为奇数,那么x-1就是偶数。
0不会改变异或值,所以结果必然取决于1,x-1为偶数,偶数个1可拆分成奇+奇或偶+偶,无论如何分配到a和b上,最终都必然使得a与b相等(要么都是1,要么都是0)。
则,关键之处在于最后一个1,谁取到最后一个1就能获胜(如果都是1,就异或给对方,如果都是0,就异或给自己)
那么,谁能取到最后一个1呢?
x必然是奇数,那么考虑y分别为奇数和偶数的情况——
y为偶数:
Alice先手取1,则x与y都变成了偶数,接下来Bob无论取什么数,Alice都和他取一样的数即可,因为x与y都为偶数,所以Bob取什么数Alice一定有相同的数可以取,最后一个1也必然落入她手中
y为奇数:
Alice先手取1,则Bob取0,此时x与y的个数都为奇数了,由上可知,Bob必胜。
Alice先手取0,则Bob取1,x与y依然都为偶数,Bob必胜
综上所述,y为偶数时Alice必胜,y为奇数时Bob必胜
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=20;
int main(){
int T,n;
scanf("%d",&T);
while(T--){
int cnt[N]={0};//存取每一位的数值
int sum=0;
scanf("%d",&n);
int x;
for(int i=1;i<=n;i++){
scanf("%d",&x);
sum^=x;
for(int j=0;j<N;j++)
cnt[j]+=x>>j&1;
}
if(!sum) puts("0");
else{
for(int i=N-1;i>=0;i--)
if(sum>>i&1){
if(cnt[i]==1) puts("1");
else if((n-cnt[i])%2==0) puts("1");
else puts("-1");
break;
}
}
}
return 0;
}