CF1383B GameGame

FxorG · 2021-07-23 10:09:23 · 题解

\text{Solution}

这种异或贪心基本都是按位分析。

考虑从高位到低位，假如这一位有 tot 个1，考虑按 tot 奇偶来分。

偶： 考虑异或能有贡献的仅有 1，所以我们只分析 1 。假如 2 个人可以都选奇数个，即对 2 个人的答案都有贡献。假如都选偶数个，那么对于 2 个人来说都抵消了。所以偶数个 1 不会影响答案。

奇： 对于奇数，假如第二个人选 x 个数，那么第一个人选 x+1 个。考虑第一个人选的是奇数（才能对答案有贡献），即 2k+1 ,那么第二个人选 2k 个，由于这样子可能胜利，所以我们保留这种情况，即 1 的数量 tot \% 4==1。为什么说可能胜利呢，因为假如有奇数个 0 ，那么完全可以让第一个人选到偶数个 1 以及奇数个 0 ，让第二个人选到奇数个 1 和偶数个 0。那么假如第一个人选 2k+2 个 1,则第二个人选 2k+1 个 1，判定方式类似于上面。但也不一定会输，因为只要有奇数个 0 ，那么就可以把奇数个 0 留给自己，使得最后有奇数个 1。（实际上就是第一个必然选偶数个数，我们要保证有奇数个 1）

假如到了最低位都没法，显然平局。

\text{Solution}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(1e5+5)

using namespace std; 
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

int t,n,a[N];

int main() {
    t=rd();
    while(t--) {
        n=rd(); int S=0;
        for(int i=1;i<=n;i++) a[i]=rd(),S^=a[i];
        bool fl=0;
        for(int i=30;i>=0;i--) {
            if((S>>i)&1) {
                int tot=0;
                for(int j=1;j<=n;j++) tot+=(a[j]>>i)&1;
                //cout<<i<<" "<<tot<<endl;
                if((n-tot)%2==0&&tot%4==3) fl=1,puts("LOSE");
                else fl=1,puts("WIN");
            }
            if(fl) break;
        }
        if(!fl) puts("DRAW");
    }   
    return 0;
}