[acwing]3421.异或数列
/*
A ^ B = X1 ^ X2 ^ ... ^ Xn
如果结果为 0,说明 A == B,平局
如果结果不为 0,只需要看结果的二进制形式最高位的 1 是谁拿到的
one[i] 记录所有 X 中位 i 为 1 的个数
zero[i] 记录所有 X 中位 i 为 0 的个数
从最高位开始遍历
如果 one[i] 为偶数,那么结果的此位为 0,直接看下一位
如果 one[i] 为奇数,那么结果的此位为 1,
如果 one[i] == 1,A 赢,否则
(手动模拟一下很清晰)
如果 zero[i] 为偶数,那么 A 赢
如果 zero[i] 为奇数,那么 A 输
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 20;
int one[N], zero[N];
int T;
void get(int x)
{
for (int i = 0; i < 20; i++) {
if (x >> i & 1) one[i]++;
else zero[i]++;
}
}
int main()
{
scanf("%d", &T);
while (T--) {
memset(one, 0, sizeof(one));
memset(zero, 0, sizeof(zero));
int n;
scanf("%d", &n);
int res = 0;
while (n--) {
int x;
scanf("%d", &x);
res ^= x;
get(x);
}
if (res == 0) puts("0");
else {
for (int i = 19; i >= 0; i--) {
if (one[i] & 1) {
if (one[i] == 1) {
puts("1");
break;
} else if (zero[i] & 1) {
puts("-1");
break;
} else {
puts("1");
break;
}
}
}
}
}
return 0;
}
标签:游戏,puts,Nim,int,res,scanf,else,zero
From: https://www.cnblogs.com/cong0221/p/17224225.html