2025_ICPC_NERC_Northern_Eurasia_Finals——F. Fragmented Nim（先碰到弹性堆的那一方，一定赢了，因为他不仅可以制造陷阱，还可以逼迫对手进入陷阱） · znzryb
## 题目大意
经典的Nim游戏规则如下。有$n$堆石头，第$i$堆最初包含$a_i$个石头。Alice和Bob轮流进行; Alice先行动。在他们的轮次中，玩家选择任意非空堆并从中移除任意正数个石头。拿到最后一块石头的玩家获胜。
在玩了很多Nim游戏之后，Alice和Bob决定稍微改变规则。在这一变体中，轮到的玩家不选择堆 — — **他们的对手为他们选择！然而，玩家仍然可以决定从那堆中移除多少石头。**
Alice仍然先手。在Alice的轮次中，Bob选择任意非空堆，然后Alice从中移除任意正数个石头。同样地，在Bob的轮次中，Alice选择任意非空堆，然后Bob从中移除任意正数个石头。
对于给定的石头堆配置，确定如果两名玩家都遵循最佳策略，谁将获胜。
## 思路讲解
这种题目是这样子的，**先碰到弹性堆的那一方，一定赢了**。先碰到弹性堆的那一方一定赢了，**这个是因为你不仅可以制造陷阱，还可以逼迫对手进入陷阱**，这个是最厉害的地方。
1. **全是 1 的情况**（$bigs = 0$）：每回合只能取 1 颗，总共 $n$ 回合，奇数轮 Alice 赢，偶数轮 Bob 赢——即 $n$ 为奇则 Alice 胜。
1. **存在 **$>1$** 的堆时**（$bigs \geq 1$）：当一个玩家被指向一个大堆（$a_i > 1$），他可以选择"全取"（消灭堆）或"留 1"（变成 size-1 堆）。这意味着他能自由控制对手下一步面对的 $ones$ 的奇偶性——因此**被指向大堆的人必赢**。
既然指向大堆 = 给对方胜利，所以"选堆方"（chooser）**一定会优先把对手指向 size=1 的堆**。双方轮流消耗 size-1 堆，直到 size-1 堆耗尽，最终被迫指向大堆的那一方就输了。
消耗 $ones$ 个 size-1 堆需要 $ones$ 轮。若 $ones$ 为偶数，Alice 仍是 mover，获得大堆 → **Alice 赢**；若 $ones$ 为奇数，Bob 是 mover → **Bob 赢**。
在变体 Nim 的纯弹性子游戏里，当前玩家必胜，本质上靠的是一个**两步连招**：
**第一步（你是操作者）：对手把你指到某个弹性堆，你把它削成 1。你制造了一个"陷阱"。**
**第二步（你变成了选堆方）：下一回合，角色互换——你来选堆，对手来操作。****你把对手指向那个你刚造出来的大小为 1 的堆****。对手被迫吃掉它，白白浪费一个回合。**
净效果：两个回合过去了，一个弹性堆被消灭，**又轮到你了**。你从 $f$ 个弹性堆的先手，变成了 $f-1$ 个弹性堆的先手。循环往复，直到只剩最后一个弹性堆，你直接清空获胜。
这个连招之所以成立，是因为**操作者和选堆方的角色每回合交替**。你当操作者时布下陷阱，下一回合你当选堆方时把对手推进陷阱。
## AC代码
AC
[https://codeforces.com/contest/2181/submission/362136313](https://codeforces.com/contest/2181/submission/362136313)
::: 源代码
```cpp
/**
* Problem: F. Fragmented Nim
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/contest/2181/problem/F
* Created: 2026-02-09 21:02:52
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> A(N);
ll cnt1=0;
for (int i=0;i<N;++i) {
cin>>A[i];
if (A[i]==1) {
++cnt1;
}
}
if (cnt1==N) {
if (N&1) {
cout<<"Alice\n";
}else {
cout<<"Bob\n";
}
return;
}
if (cnt1%2==0) {
cout<<"Alice\n";
}else {
cout<<"Bob\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2181/submission/362136313
*/
```
:::
## 心路历程（WA，TLE，MLE……）
::: AI 提示
[1 tool called]
好的，让我来分析这道 Fragmented Nim 变体博弈问题。
先读一下你的代码模板，然后我来推导策略。
这道题的关键在于理解"选堆权"和"取石权"分离后博弈结构的变化。让我推导一下：
**核心推导：**
1. **全是 1 的情况**（$bigs = 0$）：每回合只能取 1 颗，总共 $n$ 回合，奇数轮 Alice 赢，偶数轮 Bob 赢——即 $n$ 为奇则 Alice 胜。
1. **存在 **$>1$** 的堆时**（$bigs \geq 1$）：当一个玩家被指向一个大堆（$a_i > 1$），他可以选择"全取"（消灭堆）或"留 1"（变成 size-1 堆）。这意味着他能自由控制对手下一步面对的 $ones$ 的奇偶性——因此**被指向大堆的人必赢**。
既然指向大堆 = 给对方胜利，所以"选堆方"（chooser）**一定会优先把对手指向 size=1 的堆**。双方轮流消耗 size-1 堆，直到 size-1 堆耗尽，最终被迫指向大堆的那一方就输了。
消耗 $ones$ 个 size-1 堆需要 $ones$ 轮。若 $ones$ 为偶数，Alice 仍是 mover，获得大堆 → **Alice 赢**；若 $ones$ 为奇数，Bob 是 mover → **Bob 赢**。
**结论：**
- 全是 1 → Alice 赢当且仅当 $n$ 为奇
- 存在 $>1$ 的堆 → Alice 赢当且仅当 size=1 的堆数量为偶数
验证样例：
- `[1,2,3]`：有大堆，$ones=1$（奇）→ Bob ✓
- `[1]`：全是 1，$n=1$（奇）→ Alice ✓
- `[10,3,4,7,4]`：有大堆，$ones=0$（偶）→ Alice ✓
[1 tool called]
:::
::: AI 提示 2
你这个问题问得好——"到底是什么结构性原因，让碰到弹性堆的人必赢？" 以及 "为什么同样的事在经典 Nim 里不成立？"
## 核心原因：两步连招
在变体 Nim 的纯弹性子游戏里，当前玩家必胜，本质上靠的是一个**两步连招**：
**第一步（你是操作者）**：对手把你指到某个弹性堆，你把它削成 1。你制造了一个"陷阱"。
**第二步（你变成了选堆方）**：下一回合，角色互换——你来选堆，对手来操作。你把对手**指向那个你刚造出来的大小为 1 的堆**。对手被迫吃掉它，白白浪费一个回合。
净效果：两个回合过去了，一个弹性堆被消灭，**又轮到你了**。你从 $f$ 个弹性堆的先手，变成了 $f-1$ 个弹性堆的先手。循环往复，直到只剩最后一个弹性堆，你直接清空获胜。
这个连招之所以成立，是因为**操作者和选堆方的角色每回合交替**。你当操作者时布下陷阱，下一回合你当选堆方时把对手推进陷阱。
## 为什么经典 Nim 里这招不灵
经典 Nim 里，**你自己选堆、自己操作**。你可以执行第一步——把某堆削成 1。但第二步断了：
> 下一回合，对手**自己选堆**。对手凭什么要去碰你造出来的那个大小为 1 的堆？对手直接无视它，去操作别的堆。
你造了陷阱，但**你没有能力把对手推进去**。对手有完全的选择自由。
具体看 $[2, 2]$ 的经典 Nim：
- 先手把 pile 1 削成 1：$[1, 2]$。
- 后手**不碰 pile 1**，去把 pile 2 也削成 1：$[1, 1]$。
- 对称局面，先手吃一个，后手吃最后一个，**后手赢**。
先手的"陷阱"完全被后手绕过了。而在变体 Nim 里，$[2, 2]$ 先手赢，就是因为先手削成 $[1, 2]$ 后，**选堆权在先手手里**，先手直接把后手按到那个 1 上。
## 所以真正的区别是什么
| | 变体 Nim | 经典 Nim |
| --- | --- | --- |
| 操作者能布陷阱吗？ | 能（削成 1） | 能（削成 1） |
| 下一回合能把对手推进陷阱吗？ | **能**（你变成选堆方） | **不能**（对手自己选堆） |
| 两步连招成立吗？ | 成立 | 不成立 |
**决定性的差异不在于"谁碰到弹性堆"，而在于：布陷阱之后，你有没有能力强制对手踩进去。**
变体 Nim 里有这个能力（角色交替赋予的），经典 Nim 里没有（双方完全自由选择）。这就是为什么变体 Nim 的弹性子游戏退化成了简单的奇偶计数，而经典 Nim 退化不了——经典 Nim 里没有"强制"机制，信息是完全对称的，所以需要 XOR 这种更精细的不变量来刻画胜负。
:::