[CF1383B] GameGame

[CF1383B] GameGame - 博弈

Description

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

Solution

我们找到最高的一位，使得这一位上总共有奇数个 1

这意味着最后这一位一定一个是 1 一个是 0，所以这一位一定能分出胜负，如果不存在这一位那就是 DRAW

如果 1 的个数是 1,5,9,...

那么先手吃掉一个 1，就会转化为偶数的情况，先手胜利

如果 1 的个数是 3,7,11,...

那么先手吃掉一个 1，虽然转化为了偶数的情况，但是这种偶数情况两边可以再各吃一个 1，不能按上述情况简单处理

这时候需要讨论这位是 0 的数量

如果 0 的数量是偶数，那么谁吃一个 0，对面就跟着吃一个 0，这时 0 可以忽略，所以相当于只有 3 个 1，所以后手胜利

如果 0 的数量是奇数，先手先吃掉一个 0，就转化成了上一种情况，此时他自己是后手，所以总的来说，先手胜利

// Find the first pos that has odd number of 1
// if the number is 1,5,9,...
//      NEXT choose 1, and he will win
// if the number is 3,7,11,...
//      if n is odd, we have even number of 0, ignore 0, PREV will win
//      if n is even, NEXT choose 0 first, then NEXT will win
#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int j = 30; j >= 0; j--)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (a[i] & (1 << j))
                ++cnt;
        if (cnt % 2)
        {
            if (cnt % 4 == 1)
            {
                cout << "WIN" << endl;
            }
            else
            {
                if (n & 1)
                    cout << "LOSE" << endl;
                else
                    cout << "WIN" << endl;
            }
            return;
        }
    }
    cout << "DRAW" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}