题意:
有很多数字,你和对手一次拿一个,将拿到的数字与你已经有的数异或,得到新的数字,问 最后你赢还是对手赢,还是平局。
题解思考:
博弈论, 异或性质 1 ^ 1 = 0; 1 ^ 0 = 1;
异或是自己的逆运算,所以当异或两个1 时等于没有异或。
问最后的谁的值大。 那么我们可以从最高位的1的个数来入手。
① 当最高位1的个数是偶数个,那么这一位是平均, 两人一定会各拿一半的1。
② 如果最高位1的个数是奇数我们来分情况看:
有零个1, 平局, 同①。
比如有 一个1, 剩余有好多零, 那么先手胜利。
如果有 两个1, 好多零,那么平局。同①。
如果有 三个1 分情况:有偶数个零 后手胜利
有奇数个零 先手胜利
由于有四个1可以堪为有零个1, 是一个循环。据此我们可以写代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll t, n;
ll a[maxn];
void judge(ll x)
{
if(x == -1)
{
puts("DRAW");
return;
}
ll c1 = 0, c0 = 0;
for(int i = 1; i <= n; i ++)
{
if(a[i] & (1 << x)) c1 ++;
else c0 ++;
}
if(c1 %2 == 0)
{
judge(x-1);
}
else
if(c1%4 == 3 && c0%2 == 0)
{
puts("LOSE");
return;
}
else
{
puts("WIN");
return;
}
}
int main()
{
cin >> t;
while(t --)
{
cin >> n;
ll maxi = -1;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
maxi = max(maxi, a[i]);
}
ll idx = 0;
while(maxi >> idx) idx ++;
judge(idx-1);
}
return 0;
}