题目:传送门
题意
输入一个长度为 n 的序列 A,有两个人轮流进行操作,每次操作先选择序列 A 里的一个数 y,并将 y 从序列 A 删除,假设操作前选手的分数为 x,则该选手的分数变为 x^y;
起初两名选手的分数都为 0,最终谁的分数大谁赢,问最终先手是 赢 还是 输 还是 平手,假设两人都足够聪明。
思路
官方题解
首先,对于某个二进制位来说,如果这个位上的 1 的个数为偶数,那么最终双方的得分在这一位上的状态都是一样的。所以找到最高位的 1 的个数为奇数的二进制位。
找到之后,假设序列 A 在这一二进制位上为 1 的数有 x 个,为 0 的有 y 个。
有结论:当 x % 4 == 3 && y % 2 == 0 的时候,后手赢,否则先手赢。
证明:现在已经知道 x 是奇数,那么 x % 4 只能等于 1 或者 3;
当 x % 4 == 1 时,先手先选择一个 1,那么剩下的 1 的个数就是 4 的倍数,之后先手只要一直跟着后手操作就行了。
当 x % 4 == 3 时,若 y % 2 == 0,那么后手只要跟着先手操作就行了。
若 y % 2 == 1,那么先手可以先选择一个 0,之后一直跟着后手操作就能赢。
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define UI unsigned int #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF 0x3f3f3f3f #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second #define lb(x) ((x) & (-(x))) #define dbg(x) cout<<#x<<" = "<<x<<endl; using namespace std; const int N = 1e6 + 5; int n, a[N]; void solve() { scanf("%d", &n); int x = 0; rep(i, 1, n) scanf("%d", &a[i]), x ^= a[i]; if(x == 0) { puts("DRAW"); return ; } dep(i, 0, 30) { if(x >> i & 1) { int cx = 0, cy = 0; rep(j, 1, n) { if(a[j] >> i & 1) cx++; else cy++; } if(cx % 4 == 3 && cy % 2 == 0) { puts("LOSE"); } else puts("WIN"); return ; } } } int main() { int _; scanf("%d", &_); while(_--) solve(); // solve(); return 0; }