题解 CF1383B 【GameGame】

· · 题解

从高位往低位判断：

  1. 若该位 1 的个数是偶数，要么两人各选奇数个 1，要么各选偶数个 1。无论怎么选，两人在该位的异或值相同，对输赢无影响。
  2. 若该位 1 的个数是奇数，则必有一人选到奇数个 1，从而获胜。
  3. 接上，对于奇数，有 4k+3 和 4k+1 两种情况。若该位有 4k+3 个 1，且该位有偶数个 0，则后手可以完全模仿先手的选择，先手必定会选到 2k+2 个 1，而后手选到 2k+1 个 1，先手必败；若有奇数个 0，则先手可以选一个 0 从而让后手变成前述的情况，此时先手必胜。
  4. 接上，若该位有 4k+1 个 1，先手可以选一个 1，然后模仿后手的选择。对于有奇数个 0 的情况，要么最后一个 0 被后手选走然后剩下的 1 两人平分，要么 1 被选完先手选走最后的 0。无论情况如何，先手总是可以选到 2k+1 个 1 从而获胜。

最后，若所有位上的 1 的个数均为偶数则平局。

AC 代码：

#include <bits/stdc++.h>
using namespace std;

void run() {
    int n;
    cin >> n;
    vector<int> a(n);
    int s = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s ^= a[i];
    }
    if (s == 0) { // 所有位上的 1 的个数均为偶数则平局
        cout << "DRAW" << '\n';
        return;
    }
    for (int b = 30;; b--) {
        if (s >> b & 1) { // 该位 1 的个数是奇数
            int ones = 0;
            for (int v: a) if (v >> b & 1) ones++;
            int zeros = n - ones;
            cout << (ones % 4 == 3 && zeros % 2 == 0 ? "LOSE" : "WIN") << '\n';
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    for (cin >> t; t--; run());
}