[蓝桥杯] 异或数列 代码详解_alice和bob正在玩一个基于字符串的游戏,一开始,alice和bob分别拥有一个等长的

题目描述

Alice 和Bob 正在玩一个异或数列的游戏。
初始时，Alice 和Bob 分别有一个整数a 和b，初始值为0。
有一个给定的长度为n 的公共数列X1, X2, ... , Xn。
Alice 和Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：
选项1：从数列中选一个Xi 给Alice 的数异或上，或者说令a 变为a ⊕ Xi。（其中⊕ 表示按位异或）
选项2：从数列中选一个Xi 给Bob 的数异或上，或者说令b 变为b ⊕ Xi。
每个数Xi 都只能用一次，当所有Xi 均被使用后（n 轮后）游戏结束。
游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
现在双方都足够聪明，都采用最优策略，请问谁能获胜？

输入格式

每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数T，表示询问数。
接下来T 行每行包含一组询问。
其中第i 行的第一个整数ni 表示数列长度，随后ni 个整数X1, X2, ... , Xni 表示数列中的每个数。
1 ≤ T ≤ 200000, 1 ≤ sum(ni) ≤ 200000, 0 ≤ Xi < 2^20 

输出格式

输出T 行，依次对应每组询问的答案。
每行包含一个整数1、0 或-1 分别表示Alice 胜、平局或败。

题目分析：

对于给定序列，游戏的结局已经是注定的，因为两者都选取自己最优的策略

对于异或的某位 0^x=x ，1^x=翻转x   

因为给定的序列，可以将每个数字都看作为20位的二进制，高位用0补齐，并且Alice 和Bob的初始值可以看作20位的二进制，但每一位都是0，所以可以选择从高位从低位看，只要高位大则低位可以不用再去看。只要求出公共序列某一位1的总数，则可以确定先手赢或者先手输。因为如果有偶数个1，则代表翻转了偶数次，则最终结果一定还是0，即平均。 如果是奇数次，则一定会有输赢。

所以，可以开辟num[22] 标号从1开始，记录公共序列每一位对应1的总数量。

可以分析得：如果此位1的数量为偶数，则表示两个拿1的数量也是偶数，则翻转偶数次 最后结果仍为0，所以两者相等，为平局， 如果20位 num[]数组每一位1的数量都为偶数，那么可以直到公共序列异或结果一定为0 所以这个可以特判

另一种情况即为每一位1的数量为奇数，此时，需要去分析0的奇偶个数，因为0^x=x，相当于两个人在抢数，抢1或者0，如果抢到0，则自己手中的数没有变，相当于置空一轮，因为每个人手上最初的数字是0，所以想赢的话则必须去抢奇数个1，实现奇数次的翻转。所以这个时候0的奇偶个数尤其重要。

如果1的个数为奇数，0的个数为偶数，则先手者必赢，因为0相当于轮空一轮，所以先手要保证自己拿到奇数个1，对手拿到偶数个1。举个例子：想象一下Alice 和Bob手中拿着0，要去抢奇数个1实现翻转，如果公共序列某一位，有3个1，4个0，则先手者Alice 可以给Bob抢一个1，一定可以保证赢，因为给Bob抢了一个1，则剩下2个1为偶数个1，偶数个0，这个时候变成了Bob在此情况先出手，不管Bob抢什么，Alice都可以抢一个1或者0去抵消Bob的效果。比如Bob抢0，则Alice抢0抵消，相当于轮空这一轮，如果Bob抢1，则Alice可以抢1给Bob去抵消Bob的做法，但事实上，采取最优策略，Bob一定要抢0，才有赢的机会。但最终Bob依然会输。

但是如果1的个数为奇数，0的个数也为奇数，则先手Alice必输，如果先手着抢1，将手中的0翻转一次，则还剩下偶数个1，但是0的个数为奇数，这个时候Bob最优策略一定选择抢0，轮空，等到只剩下1时，一定是Alice先手，此时是偶数个1，且Alice手中的数也为1 所以无论Alice这个时候怎么选，Bob都可以使自己手中的数0翻转，使得Alice手中的数1也翻转。

但是要注意：做的时候没有特判1的数目为1一个的情况，这个情况要单独判断，因为如果只有1个1，则两人一共只可以翻转一次，先手一定要抢1，剩下的全是0，不管0是奇数还是偶数，先手必赢！

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[23];//记录1-22位 1的数目 
ll a;
//count 的功能即数一数整个公共序列，每个数字的每位（二进制）有共有多少个1，存在num数组 
void count(ll x){
	int cnt=1;//指针index
	while(x){
		if(x&1)	num[cnt]++;//如果最低为1 则记录下来+1 
		cnt++; //之前用偷懒 想在上一步 num[cnt++]++ 直接把cnt+1 发现如果这一位不是0 仍然需要将cnt往后移 
		x=x>>1;//右移一位  次低位移到低位 
	} 
}
int main()
{
	int N;
	ios::sync_with_stdio(0);cin.tie(0); //  解除cin与cout的绑定 加快执行效率  不用也可以AC
	cin>>N;
	while(N--){
		memset(num,0,sizeof(num));
		int t;
		ll sum=0;
		cin>>t;
		for(int i=0;i<t;i++){
			cin>>a;
			count(a);//数一数a每个位的1的数目
			sum=sum^a;//记录sum 特判 如果sum=0 则一定平局  
		}
		if(!sum) puts("0");// 特判 
		else{
			//题目数据最多20位，也就是最高就是第20位，从高位开始比 
			for(int i=20;i>0;i--){
				if(num[i]==1){//这里需要特判一下， 有1个1的话 与0的奇偶个数无关了！
					puts("1");
					break;
				}
				else if(num[i]%2==1){ //奇数个1  
					if(t%2==1){
						puts("1");//表示有奇数个1，偶数个0 则先手必赢， 
						break;
					}
					else {
						puts("-1");
						break;
					}
				}
			}
		}
	}
	return 0;
}