试题 历届真题 异或数列【第十二届】【省赛】【A组】

注意：每一轮都是Alice先手 不管Alice选择一 还是二 Bob 两个选项都可以再次选择 

如果平局 a^b=0 a和b相同 即为X1^X2^X3^....Xn=0;

由于是二进制 只要最高位为一的个数只有一个 先手赢

如果最高位为一的个数为奇数 且总数列数为奇数 先手胜 自己可以举几个例子、

如果最高位为一的个数为奇数 且总列数为偶数 后手胜

如果最高位为一的个数为偶数 比较不出 比较次高位

基础知识：

按位与：a&b是把a和b都转换成二进制数然后再进行与的运算；

逻辑与：a&&b就是当且仅当两个操作数均为 true时，其结果才为 true；只要有一个为零，a&&b就为零。

a^=b等价于a = a^b，其中^是位异或运算，即将a与b的对应位进行异或运算，同为0或者同为1时，对应位结果为0；否则为1。
 

假设，a的值为二进制的1010，b的值为二进制的1100，那么a^b = 0110

 

#include<bits/stdc++.h>
using namespace std;
int cnt[24];
void slove(long long x)
{
	int k=1;
	while(x)
	{
		if(x&1)
		{
			cnt[k]++;
			
			
		}
		x=x>>1;
		k++;
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		int sum=0;
		memset(cnt,0,sizeof(cnt));
		for(int j=1;j<=a;j++)
		{
			long long b;
			cin>>b;
			slove(b);
			sum^=b;
		}
		if(sum==0)
		{
			cout<<0<<endl;
		}
		else
		{
			for(int i=20;i>0;i--)
			{
				if(cnt[i]==1)
				{
					cout<<1<<endl;
					break;
				}
				else
				{
					if(cnt[i]%2==1&&a%2==1)
					{
						cout<<1<<endl;
						break;
					}
					if(cnt[i]%2==1&&a%2==0)
					{
						cout<<"-1"<<endl;
						break;
					}
				}
			}
		}
	}
	return 0;
}