题解：CF1383B GameGame

czy114514 · 2026-07-21 09:45:48 · 题解

设两人最终得分A,B，所有元素异或和为X=\oplus_{i=1}^n a_i，那么有A\oplus B=X,如果X=0，说明无论怎么弄，A,B每一位都必然相同，是平局。

如果某一位不为0，但是它高位全为0，说明这一位是决定谁先手必胜的。并且这一位为1的数字的个数一定是奇数。

那么如果要先手必胜，有一种方法·就是第一个人拿一个，对方只要再拿同类型的数字，自己就模仿他，并且要保证最终为1，所以模仿的次数一定是偶数，设为2m,那么总数一定是4m+1。

那么如果模仿轮次是奇数的话，即总个数为4m+3，这样并不是最优的。很显然如果别的数字没有那就先手必败了，所以应该通过走这一位为0的数字尝试改变。

如果这一位为0的数字是奇数，先手可以先选一个这一位为0的数字，接下来只要后手选择这一位为1的数字，先手就模仿他选。如果后手选择这一位为0的数字，先手也模仿他选。能够保证最后一个这一位为0的数字是被先手选走的。并且后手选了偶数个，先手选了奇数个这一位为1的数字。先手必胜。

反之如果这一位为0的数字是偶数的话，那么先手走哪一个，后手都可以模仿他，并且最后一个这一位为1的是被先手拿走的，先手总共拿了偶数个，先手必败。

代码

#include <bits/stdc++.h>
using namespace std;
/*
      /\_/\
     ( =o.o= ) *
      / >  \>
*/
#define ll long long 
#define i128 __int128_t
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define ull unsigned long long
#define VI  vector<int>
#define VII vector<VI>
#define VL  vector<ll>
#define VLL vector<VL>
const int N=1e5+10;
ll a[N];
void sol() {
    int n;cin>>n;
    ll xr=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        xr^=a[i];
    }
    if(!xr) cout<<"DRAW\n";
    else{
        int idx;
        for(int i=32;i>=0;i--){
            if((xr>>i)&1){
                idx=i;
                break;
            }
        }
        ll s=0;
        for(int i=1;i<=n;i++){
            if((a[i]>>idx)&1){
                s++;
            }
        }
        if((s-1)%4==0){
            cout<<"WIN\n";
        }else{
            if((n-s)&1){
                cout<<"WIN\n";
            }else{
                cout<<"LOSE\n";
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}