D. GameGame
题意
有一堆数字
两个人轮流拿
最后两人手里的数的异或和最大的人取胜
题解
对于所有数的most significant bit 统计 有x个1 y个0
假设x是偶数那么对于这一位数，两人最后拿到的异或和相同
去掉这一位以下一位作为most significat bit
若当前x为奇数需要讨论
若当前这位x%4==1
那么先手可以先拿一个1然后模仿后手每次的决策 最后先手这位数的异或和更大
比如x=5, 被轮流取走后先手有3个1 而后手只有2个1
若当前这位x%4==3
假设y%2==0
后手一直模仿先手每次的决策最后会多出来一个1 先手必须拿走
最后先手手中有偶数个1 后手有奇数个1后手更大
若y%2==1那么 先手可以先拿多出来的0,让后手变成先手 两人角色互换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
ll data[Max];
int main() {
int t;cin>>t;
while(t--){
int n;cin>>n;bool Lose=0,Win=0;
for(int i=0;i<n;i++)cin>>data[i];
for(ll shift=32;shift>=0;shift--){
ll msb=(1ll<<shift);
int one=0,zero=0;
for(int i=0;i<n;i++){
if(msb&data[i])one++;
else zero++;
}
if(one%2==0)continue;
if(zero%2==0&&one%4==3)Lose=1;
else Win=1;
break;
}
if(Lose)cout<<"LOSE"<<endl;
else if(Win)cout<<"WIN"<<endl;
else cout<<"DRAW"<<endl;
}
}
|