蓝桥杯2021省赛A组
I. 异或数列
可以参考：寒假每日一题07 | 【蓝桥杯省赛】异或数列 StarryCoding.109
位运算(异或)，博弈论。两个二进制数按位比较大小，从高位到低位比较，当出现不同时，位为1的数比较大。
对于某一确定的二进制数的某一位，异或0对其没有影响，异或1会使该位取反。考虑Alice和Bob在某一位层的二进制位(a, b)，(a, b)初始为(0, 0)，异或1操作会使其中的某一个元素取反，偶数次的异或1之后恒有a==b，所以当异或数组某一位层的1总数为偶数时，这一位层不会产生区别。
当有奇数个1时，如果只有一个1，则Alice直接获胜，否则分两种情况：有奇数个0；有偶数个0. 一个可以观察到的事实是：当某一人a的操作使得当前所剩1和0都为偶数时，下一个操作的人b最后一定会输，因为在这之后，a只要保持和b取相同的异或位，最终一定会取到最后(决定性的)一个1. 所以对于奇数个0(同时也有奇数个1)，无论Alice取什么，Bob只需取相反的位，就能让Alice陷入偶0偶1，Alice输；对于偶数个0，Alice只需要取1，就能让Bob陷入偶0偶1，Alice赢。
注意数组a[N]需要开long long，否则会爆int.
#include <bits/stdc++.h>
using namespace std;
int t, n;
const int N = 200010;
long long a[N];
int main(){
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int res = 0;
for(int i = 100; i >= 0; i--){
int cnt = 0;
for(int j = 1; j <= n; j++){
int x = a[j] >> i & 1;
if(x) cnt++;
}
if(cnt % 2 == 0) continue;
else{
if(cnt == 1) res = 1;
else if(n % 2 == 0) res = -1;
else res = 1;
break;
}
}
cout << res << endl;
}
return 0;
}