CF1990A Submission Bait 题解

题意回顾

Alice 和 Bob 在一个长度为 $n$ 的数组 $a$ 上博弈。初始 $mx = 0$。每轮操作：选择一个 $a_i \ge mx$，将 $mx$ 更新为 $a_i$，并将该位置置为 $0$。无法操作者输。Alice 先手，问 Alice 是否有必胜策略。

关键观察

由于每次操作后 $mx$ 只增不减，玩家后续只能选择 $\ge mx$ 的数。一旦某个较小值被跳过，就再也无法被选取。

因此游戏的核心在于最大值：如果先手直接选取最大值 $M$，则 $mx$ 变为 $M$，后续双方都只能选 $M$。游戏变为双方轮流取 $M$，直到 $M$ 取完，无法继续的一方输。

如果最大值 $M$ 出现奇数次，先手取走最后一个 $M$，后手无法操作，先手胜。
如果最大值 $M$ 出现偶数次，后手取走最后一个 $M$，先手无法操作，先手败。

可能有人会问：先手能否不选最大值，而选一个较小的值来改变局面？
如果先手选较小值 $x < M$，$mx = x$。此时后手可以直接选 $M$（因为 $M \ge x$）。局面转为：后手选了第一个 $M$，相当于后手在"最大值游戏"中变成了先手。此后双方只能选 $M$。若 $M$ 有偶数个，后手（作为 $M$ 的新先手）会取到最后一个 $M$，先手反而输。若 $M$ 有奇数个，后手选 $M$ 后留给先手偶数个 $M$，先手同样输。所以先手选非最大值永远不如直接选最大值。

综上：Alice 必胜当且仅当数组中的最大值出现奇数次。

正确解法

1. 读入数组，找到最大值 $mx\_val$。
2. 统计 $mx\_val$ 的出现次数 $cnt$。
3. 若 $cnt$ 为奇数，输出 YES；否则输出 NO。

时间复杂度 $O(n)$ 每测试用例，足够通过 $t \le 10^3,\; n \le 50$ 的限制。

参考代码

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int mx = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > mx) mx = a[i];
        }
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (a[i] == mx) cnt++;
        cout << (cnt % 2 ? "YES" : "NO") << '\n';
    }
    return 0;
}

备注

原给出代码的判定逻辑为"若所有值的出现次数均为奇数则 NO，否则 YES"，该结论与样例不符，存在错误。正确结论仅需关注最大值出现次数的奇偶性。