1965A - Everything Nim 官方标程思路 题解

一、标程核心思路翻译与讲解

1. 游戏规则

• 每次选择 $k$，满足 $k \le$ 最小非空堆的大小
• 对所有非空堆同时移除 $k$ 个石子
• 无法操作者输，Alice 先手

2. 标程关键推导

1. 若最小堆大小 = $1$ 玩家只能选 $k=1$，所有堆减 $1$，交换先手，重复直到最小堆 $\ge 2$。

2. 若最小堆大小 $x \ge 2$ 当前先手必胜！

   • 选 $k=x$ 可直接让对手进入必败态
   • 即使不行，选 $k=x-1$ 强制对手只能选 $k=1$，依然必胜

3. 标程最终结论（最核心）

只需要计算两个值：

• $a$：石子堆的最大值
• $b$：正整数的 MEX（最小的、没出现在石子堆中的正整数）

胜负判断：

1. 若 $b > a$ 游戏会一直被迫选 $k=1$ 直到结束，$a$ 的奇偶性决定胜负

   • $a$ 奇数 → Alice 胜
   • $a$ 偶数 → Bob 胜

2. 若 $b \le a$ 游戏会进入最小堆 $\ge 2$ 的先手必胜态，$b$ 的奇偶性决定胜负

   • $b$ 奇数 → Alice 胜
   • $b$ 偶数 → Bob 胜

二、MEX（最小未出现正整数）计算方法

例子：

• $[3,3,3] \rightarrow$ 没出现的最小正整数是 $1 \Rightarrow b=1$
• $[1,7] \rightarrow$ 没出现的最小正整数是 $2 \Rightarrow b=2$
• $[1,2,3] \rightarrow$ 没出现的最小正整数是 $4 \Rightarrow b=4$

计算方法：

1. 数组去重 + 排序
2. 从 $1$ 开始找第一个缺失的数

三、C++ AC 代码（对标标程，$O(n\log n)$）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        ll max_a = 0;
        
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            max_a = max(max_a, a[i]);
        }
        
        // 去重 + 排序，求 MEX（最小未出现正整数 b）
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        
        ll mex = 1;
        for (ll x : a) {
            if (x == mex) mex++;
            else break;
        }
        
        // 标程核心判断
        if (mex > max_a) {
            // 看最大值的奇偶
            if (max_a % 2 == 1) cout << "Alice\n";
            else cout << "Bob\n";
        } else {
            // 看 mex 的奇偶
            if (mex % 2 == 1) cout << "Alice\n";
            else cout << "Bob\n";
        }
    }
    return 0;
}

四、样例输入输出验证

输入

7
5
3 3 3 3 3
2
1 7
7
1 3 9 7 4 2 100
3
1 2 3
6
2 1 3 4 2 4
8
5 7 2 9 6 3 3 2
1
1000000000

输出

Alice
Bob
Alice
Alice
Bob
Alice
Alice

完全正确！

五、复杂度说明

• 时间：$O(n\log n)$（排序）
• 空间：$O(n)$
• 满足题目限制：$n \le 2 \times 10^5$，$t \le 10^4$

六、标程核心公式总结

• $a = \max(a_i)$

• $b = \text{MEX}(\{a_i\}, \text{exclude } 0)$

• 若 $b > a$：$\boldsymbol{a \% 2 == 1}$ → Alice

• 否则：$\boldsymbol{b \% 2 == 1}$ → Alice