最近刚好在刷博弈论，看到这道题没有题解，所以刚好来水一发
题目链接
[蓝桥杯 2021 省 A] 异或数列
题目描述
Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一 个整数 \(a\) 和 \(b\), 有一个给定的长度为 \(n\) 的公共数列 \(X_{1}, X_{2}, \cdots, X_{n}\) 。
Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种:
选项 1: 从数列中选一个 \(X_{i}\) 给 Alice 的数异或上, 或者说令 \(a\) 变为 \(a \oplus X_{i}\) 。（其中 \(\oplus\) 表示按位异或）
选项 2: 从数列中选一个 \(X_{i}\) 给 Bob 的数异或上，或者说令 \(b\) 变为 \(b \oplus X_{i}\) 。
每个数 \(X_{i}\) 都只能用一次, 当所有 \(X_{i}\) 均被使用后（\(n\) 轮后）游戏结束。游戏结束时, 拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
现在双方都足够聪明，都采用最优策略，请问谁能获胜?
输入格式
每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数 \(T\)，表示询问数。
接下来 \(T\) 行每行包含一组询问。其中第 \(i\) 行的第一个整数 \(n_{i}\) 表示数列长度，随后 \(n_{i}\) 个整数 \(X_{1}, X_{2}, \cdots, X_{n_{i}}\) 表示数列中的每个数。
输出格式
输出 \(T\) 行，依次对应每组询问的答案。
每行包含一个整数 \(1\)、\(0\) 或 \(-1\) 分别表示 Alice 胜、平局或败。
样例 #1
样例输入 #1
4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580样例输出 #1
1 0 1 1提示
对于所有评测用例, \(1 \leq T \leq 2\times 10^5,1 \leq \sum\limits_{i=1}^{T} n_{i} \leq 2\times10^5,0 \leq X_{i}<2^{20}\) 。
蓝桥杯 2021 第一轮省赛 A 组 G 题。
题目解释
- 读完了之后发现完全没说a和b是什么东西，看完样例发现，a和b默认应该为0
性质
- 可以看到，双方的选择最终一定会把所有的数字选择光，而且根据异或的性质，异或之后得到的结果和数字的异或顺序无关，所以我们最后得到的Alice和Bob的数字\(A\)和\(B\)一定满足：
- \(A\oplus B = X_1 \oplus X_2 \oplus...\oplus X_n\)
- 可以看出，假如将所有\(X_i\)进行二进制拆分，并且统计每一位的1的个数，设这个统计数组为\(ans\)，那么Alice和Bob的策略就是抢\(ans\)的最高位的1
- 如果\(ans\)最高位的1的个数为1个，那么一定是先手必胜。因为只要Alice先手抢到了这个贡献了1的这个数字，(也就是最大的数字)，那么剩下的过程无论Alice和Bob如何选，无论异或在\(A\)或者\(B\)上，最高位的这个1都是无法被抵消掉的，在最终的\(A\)中都有最高位的这个1，而\(B\)的同一位为0，所以\(A\)一定大于\(B\)。
- 如果最高位的1的个数为奇数个（非1个），那么显然在Alice选择了一个高位1之后，他们谁都不会优先去选择能为最高位贡献1的数字了，因为此时能为最高位贡献1的数字剩余一定是偶数个，如果Bob先选了某一个高位1和\(B\)/\(A\)异或，那么Alice一定会选择一个高位1去跟\(B\)/\(A\)异或，来抵消掉刚刚Bob的操作对于最高位的影响。对于Alice也是如此。
- 所以此时两人一定都会开始选择一些“无关紧要”的数字，直到某一方不得不选择对于最高位有影响的数字
- 所以此时:如果n为偶数，那么后手赢
- 如果n为奇数，那么先手赢
- 如果最高位的1的个数为偶数个，那么一方选择了某一个为最高位贡献了一个1的数字时，另一方一定会紧随其后选择另一个也为最高位贡献了一个1的数字，这样使得在\(A\)和\(B\)中的这一位抵消掉，否则会让自己陷入劣势，所以我们应该看次高位，如果仍为偶数则看次次高位，直到某一个位的“1的个数”是奇数为止。
代码
#include<bits/stdc++.h>
#define re register
#define ll long long
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define dec(i,j,k) for(re int i=j;i>=k;i--)
using namespace std;
const int maxn = 2e5+10;
inline int read(){
re int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+(ch^48); ch=getchar();}
return x*f;
}
inline ll re_ad(){
re ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+(ch^48); ch=getchar();}
return x*f;
}
int T,n;
ll a[maxn];
int bit[32],highbit;
int cnt;
inline void div(ll x){
cnt=1;
while(x){
if(x&1) bit[cnt]++;
cnt++;
x>>=1;
}
highbit = max(highbit,cnt);
}
int main(){
T=read();
inc(t,1,T){
n=read();
memset(bit,0,sizeof(bit));
highbit=0;
ll check = 0;
inc(i,1,n){
a[i]=re_ad();
check^=a[i];
div(a[i]);
}
if(!check){
puts("0");
}else{
dec(i,highbit,1){
if(bit[i]&1){
if(bit[i]==1) puts("1");
else if(n&1) puts("1");
else puts("-1");
break;
}
}
}
}
}
/*
1
5 4 2 8 7 3
*/