2025_ICPC_NERC_Northern_Eurasia_Finals——F. Fragmented Nim（先碰到弹性堆的那一方，一定赢了，因为他不仅可以制造陷阱，还可以逼迫对手进入陷阱）

题目大意

经典的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 胜。

2. 存在 $>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

源代码

/**
 * 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 胜。
2. 存在 $>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 这种更精细的不变量来刻画胜负。