【异或数列——博弈论】

题目

思路

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;
                }
            }
        }
    }
}