GameGame

Created by LXC on Wed Mar 13 16:10:30 2024

https://codeforces.com/problemset/problem/1383/B

ranting: 1900

tag: bitmasks, constructive algorithms, dp, games, greedy, math

problem

有一个长度为N的a数组，初始两人的得分都为零，
两个人轮流从其中拿走一个数，再将自己目前得分与拿走的数异或，最终得分高者获胜。
问先手有没有必胜策略，必胜输出“WIN”，必败输出“LOSE”，平局输出“DRAW”。

多组数据。

solution

我们需要异或和最大，可以从二进制高位起逐位比较。

设$a_{i,j}$为$a_i$的高位第j位的值。

从高位到低位开始枚举j，统计所有$a_i$其第j位为1的个数$\sum \limits_{0\le i < n} a_{i,j}$，记为$c_1$，以及为0的个数$n - \sum \limits_{0\le i < n} a_{i,j}$，记为$c_0$

如果$c_1$为偶数个，由于”奇数+奇数=偶数，偶数+偶数=偶数”，所以，两个人拿的1的个数其奇偶性相同。所以两个人最终结果的二进制在此位都是1或都是0,是相同的。我们直接比较下一位。

如果$c_1$为奇数个

• 若为1 5 9 13 ...这种除以2向下取整是偶数$\lfloor \frac{c_1}{2} \rfloor \equiv 0\pmod 2$的情况，必赢。先手拿1, 此时有偶数个1,然后对手拿什么你就拿什么，如果是奇数个0,对手拿了最后一个0,你就拿1。最后你拿的1的个数是奇数个。
• 若为3 7 11 15 ...这种除以2向下取整是奇数$\lfloor \frac{c_1}{2} \rfloor \equiv 1\pmod 2$的情况，$c_0$为奇数则赢，否则输。如果没有一个0，那么这种情况，先手会拿偶数个1,后手拿奇数个1,先手必败。如果有一个0，先手拿一个0,然后后手是必败态。如果有两个0，先手不能拿0，否则后首也拿0，先手就成了必败态，而此时先手无论拿什么，后首也跟着拿什么。先手仍然必败，这种情况可以推广到0出现偶数次的情况，所以只有出现奇数个0的情况下才能获胜。

证明？

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i:a) cin >> i;
    for (int i=31; i>=0; i--) {
        int c1 = 0, c0 = 0;
        for (int j:a) {
            if (j>>i&1) c1++;
            else c0++;
        }
        if (c1%2) {
            if (c1/2%2) {
                cout << (c0%2?"WIN\n":"LOSE\n");
            } else {
                cout << "WIN\n";
            }
            return ;
        }
    }
    cout << "DRAW\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}