【异或数列——博弈论】

题目

思路

1. 异或和为0（即每一位都有偶数个1）：平局
2. 最高有效位只有唯一的1：先手必胜
3. 最高有效位有奇数个1，偶数个0：先手必胜
   1. 若先选1产生优势，则剩下偶数个1，偶数个0：对手选1我选1抵消他的影响，对手选0我选0，必胜
4. 最高有效位有奇数个1，奇数个0：先手必败
   1. 若先选0，则对手拿到状态3，必败，不可取
   2. 若先选1，则剩下偶数个1，奇数个0：对手坚持拿0，我不敢拿1（不然对手会得状态3）只能拿0，但是最后一个0被对手拿走，最后我拿走两个1，剩下奇数个1，必败
   3. 因此先手必败

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int main()
{int t;cin >> t;while(t--){int cnt[N] = {0};int sum = 0;int n;cin >> n;for(int i = 1; i <= n; i++){int x;cin >> x;sum ^= x;for(int i = 0; i < N; i++)cnt[i] += x >> i & 1;}if(!sum) cout << "0\n";else{for(int i = N-1; i >= 0; i--){if(sum >> i & 1){if(cnt[i] == 1 || (n - cnt[i]) % 2 == 0) cout << "1\n";else cout << "-1\n";break;}}}}
}