题解 | #浮木博弈#

该问题属于博弈论中的公平博弈（Impartial Games）变体，但由于其对取物顺序的严格限制（必须从第一个非空堆取样），其核心逻辑不同于标准的 Nim 博弈，而更接近于前缀控制博弈。

一、问题分析

问题的核心约束在于必须从第一个非空堆取走任意正整数张全家福。这意味着，游戏的进行路径在很大程度上是被“序”约束的。只有当第 $i$ 堆被取空后，玩家才能操作第 $i+1$ 堆。

这一约束改变了博弈的自由度：在标准 Nim 博弈中，玩家可以任选一堆来改变异或和；但在本题中，每一堆的决策权力是按顺序移交的。因此，博弈的关键变成了：谁能掌握对“关键堆”的控制权。

二、算法：关键堆与控制权转移

1. “1”的强制性

若第 $i$ 堆的数量 $a_i = 1$ ，当前轮次的玩家没有选择，必须取走这一张。这导致该玩家不可避免地将操作下一堆（第 $i+1$ 堆）的机会交给了对手。

2. “ $a_i > 1$ ”的决策权（控制堆）

若第 $i$ 堆的数量 $a_i > 1$ ，当前玩家拥有博弈主动权。该玩家可以采取以下两种策略之一：

策略 A（全部取走）：取走整堆 $a_i$ 。此时，下一堆 $a_{i+1}$ 的先手权交给对手。
策略 B（保留 1 个）：取走 $a_i - 1$ 张。此时，第 $i$ 堆还剩 1 张，轮到对手时由于只能从第一个非空堆取，对手必须取走这最后的 1 张。随后，当前玩家重新获得第 $i+1$ 堆的先手权。

结论：第一个遇到 $a_i > 1$ 的玩家可以根据后序子游戏的胜负情况，自由决定是由自己还是由对手开启下一堆。在最优策略下，第一个遇到 $a_i > 1$ 的玩家必然能够通往获胜状态，除非该堆已经是最后一堆。若是最后一堆且 $a_n > 1$ ，当前玩家直接取完获胜。

3. 边界情况：全为 "1"

若序列中不存在 $a_i > 1$ 的堆（即所有 $a_i = 1$ ），则每位玩家都被强制交替执行操作。此时胜负完全取决于堆的数量 $n$ 的奇偶性：

$n$ 为奇数：Alice 获胜。
$n$ 为偶数：Bob 获胜。

三、代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        int winPos = -1;
        for (int i = 1; i <= n; i++) {
            int a;
            cin >> a;
            if (winPos == -1 && a > 1) {
                winPos = i;
            }
        }
        if (winPos != -1) {
            cout << (winPos % 2 == 1 ? "Alice\n" : "Bob\n");
        } else {
            cout << (n % 2 == 1 ? "Alice\n" : "Bob\n");
        }
    }
}

题解 | #浮木博弈#

一、 问题分析

二、 算法：关键堆与控制权转移