题目描述
注意几点:
1.Alice 和 Bob都可以选择是对自己异或还是对对方异或
2.平局情况:Alice 和 Bob的值最后相等,即是0^0^a[1]^a[2]^…a[n]=0
3.x^0=x;x^1翻转
因而只有高位是1再^x时x才可能变大,因而考虑对所有a[n]转成2进制后各位1的个数进行统计(毕竟一个数的二进制只能为1或0,放在一个数组里统计也不会出现冲突)
结论:
从最高位开始遍历:
如果第i位上1的个数为 1,则一定是Alice赢;
如果第i位上1的个数为大于1的奇数,0的个数为偶数,则Alice赢;
如果第i位上1的个数为大于1的奇数,0的个数为奇数,则Bob赢;
如果第i位上1的个数为偶数,考虑下一位 。
原因:
如果第i位上1的个数为1,Alice肯定第一个就抢它;
如果第i位上1的个数为非1的奇数,谁拿到最后一个1,谁就赢(此时双方要么全奇数次翻转是1,此时让对方偶数次翻转变成0;要么双方全偶数次翻转是0,此时让自己翻转变1)
如何使拿到最后一个1?通过插入0。
因为双方都是最优解所以0都会被用完
0的个数 = 总个数(n) - 1的个数
如果在最后一次翻转之前插入偶数个0,则最后一次1的翻转权还是Alice(n为奇数)
如果在最后一次翻转之前插入奇数个0,则最后一次1的翻转权则是Bob(n为偶数)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int num[23];
int t,n;
void pre(long long a)
{
int cnt=1;
while(a)
{
if(a&1)
num[cnt]++;
cnt++;
a>>=1;
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(num,0,sizeof(num));
int sum=0;
for(int i=0; i<n; i++)
{
long long a;
cin>>a;
pre(a);
sum^=a;
}
if(sum==0)
cout<<0<<endl;
else{
for(int i=20; i>0; i--)
{
if(num[i]==1)
{
cout<<1<<endl;
break;
}
else if(num[i]%2==1)
{
if(n%2==1)
{
cout<<1<<endl;
break;
}
else if(n%2==0)
{
cout<<-1<<endl;
break;
}
}
}
}
}
return 0;
}