思路:
如果最高位为1的只有1个,那么谁先手谁胜
(1)如果有偶数个则看次高位,若所有数异或和为0,相当于从最高位到第一位的1都为偶数,即为平局
(2)如果有奇数个
(i)0有偶数个,先手胜
(ii)0有奇数个,后手胜
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int num[N];
void init(int x)
{
int j = 1;
while (x)
{
if (x & 1)num[j]++;
j++;
x >>= 1;
}
}
int main()
{
int T; cin >> T;
while (T--)
{
memset(num, 0, sizeof(num));//不要忘记初始化
int n, x; cin >> n; int sum = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &x);
init(x);
sum ^= x;
}
if (sum == 0)cout << 0 << endl;//相当于从最高位到第一位的1都为偶数
else
{
for (int i = 20;i>=1; i--)
{
if (num[i] == 1)//最高位1为1个
{
cout << "1" << endl; break;
}
if (num[i] & 1)//最高位1为奇
{
if ((n - num[i]) % 2 == 0)//最高位0为偶
{
cout << "1" << endl; break;
}
else
{
cout << "-1" << endl; break;
}
}
}
}
}
}