蓝桥杯2021年第十二届省赛真题-异或数列
题目 2021年蓝桥杯第十二届省赛真题-异或序列
题目描述
Alice和Bob正在玩一个基于异或数列的游戏。初始时，Alice和Bob分别持有两个整数a和b，共同拥有一段长度为n的公共数列X₁, X₂, …, Xₙ。游戏规则如下：双方轮流进行操作，Alice先手，每一步可以选择以下两种操作之一：
操作1：从数列中选择一个Xi，将其与Alice的数a进行按位异或运算，即a = a ⊕ Xi。
操作2：从数列中选择一个Xi，将其与Bob的数b进行按位异或运算，即b = b ⊕ Xi。
需要注意的是，每个Xi只能使用一次，当所有Xi都被使用完毕（经过n轮操作后）时，游戏结束。游戏结束时，拥有较大数值的一方获胜，若双方数值相等则判定为平局。
假设双方均采取最优策略，那么谁能获胜？
输入
每个测试用例由多组独立的查询构成。各组查询之间互不影响。输入的第一行给出一个整数T，表示查询总数。以下T组查询，其中第i组查询的第一项为一个整数ni，表示数列长度，其余ni个整数X1, X2, · · · , Xni表示该组查询的具体内容。
输出
输出 T 行，依次对应每组询问的答案。
每行
样例输入
样例输出
提示
【评测用例规模与约定】
对于所有评测用例，1 ≤ T ≤ 200000，1 ≤ ∑Ti=1 ni ≤ 200000，0 ≤ Xi < 220。
题目分析：
首先明确，为什么给定一个数列，游戏的结局是确定的呢？
A赢的意思是：A能采取某种策略，不管B作何应对，A保证自己一定能赢；
B赢的意思是：B能采取某种策略，不管A作何应对，B保证自己一定能赢；
对于异或：0^X ——保持X ； 1^X——翻转X ;
偶数次翻转将回到原来的状态，即与偶数个1异或将保持不变
首先，最后两个结果数AB等于式ab^sum，其中sum为给定数列所有数的异或和，sum = X1X2...Xni。
所以如果是平局，即A = B，则A^B=0，等价于 sum = 0 （输出：“0”） 。
在处理sum不等于0的情况时，基于按位异或的特性，最终需要比较A和B的大小关系。比较时应从最高位开始，若最高位相同，则依次比较次高位，依此类推。其中num[i]记录第i位上1的总数量；
先说结论：
如果某一位的num[ i ]为偶数，则游戏结果的这一位一定相等，考虑下一位 ；
如果第i位上1的个数为 1，则一定是先手赢**（输出：“1”）** ；
如果第i位上1的个数为大于1的奇数，0的个数为偶数，则先手赢**（输出：“1”）** ；
如果第i位上1的个数为大于1的奇数，0的个数为奇数，则后手赢**（输出：“-1”）** ；
下面分析原因：
如果某一位的num[i]为奇数值，即该位上有奇数个1参与与a和b的异或操作，例如，当该位上有5个1参与异或操作时，由于0在异或操作中不会改变状态，因此，（a,b）的状态转移过程一定是：
在游戏进行过程中，当状态处于平局状态（无论是（0，0）还是（1，1））时，Alice和Bob轮流进行操作。最终决定胜负的玩家是拥有最后一次改变状态的玩家（也就是最后一个1的拥有者），他们将赢得整个游戏。
如何让最后一个1轮到自己身上？这就要运用0，因为0不会改变数的大小，相当于让自身“轮换次数减少一次”。还是考虑上面5个1的情况：
当在最后一次翻转之前（无论在什么位置）放置偶数个0时，最后一次1的翻转权被赋予了先手 Alice，因此先手获胜；
当在最后一次翻转之前（无论在什么位置）添加奇数个零时，后手Bob获得了最后一次1的翻转权，从而确保后手胜出。
因为Alice和Bob都具有智慧，面对奇数个1时，Bob必须抢位，否则将失去主动权，而Alice也必须采取抢位策略，以确保最终决定权回到自己手中。然而，由于0的数量有限，胜负结果完全由0的奇偶性决定。
就整体来看，这道题目未对某类典型的算法或数据结构进行考查，但对按位异或的性质及其逻辑分析能力则有一定要求。测试数据的难度较大，而暴力法在得分上仍具有一定难度。
实现代码如下：
//2021省赛G-异或数列
#include <iostream>
#include <cstring>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _for(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 200000+10;
int T,n,ans,a,b,sum;
int x[N],num[20+5];
void count() //存储各位上1的个数
{
sum=0;
memset(num,0,sizeof(num));
rep(i,1,n){
int xi=x[i];
sum^=xi;
int pos=0;
while(xi){
if(xi&1) num[pos]++;
pos++;
xi>>=1;
}
}
}
void solve(){
count();
if(!sum){
cout<<0<<endl;
return;
}
else{
for(int i=19;i>=0;i--){
int num0=n-num[i];
if(num[i]%2==0){
continue;
}
else if(num[i]==1){
cout<<1<<endl;
return;
}
else{
if(num0%2==0){
cout<<1<<endl;
return;
}
else{
cout<<-1<<endl;
return;
}
}
}
}
cout<<ans<<endl;
}
int main(){
cin>>T;
while(T--){
cin>>n;
rep(i,1,n){
cin>>x[i];
}
solve();
}
return 0;
}因为输入数据量大，加上下面语句后速度会快一点：
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);