「一本通 6.7 练习 5」取石子游戏

形式化题目

给定一排 $n$ 堆石子，石子数分别为 $a_1, a_2, \dots, a_n$ 。两名玩家轮流操作。每一步操作者必须且只能从当前序列的最左端或最右端的一堆中取走任意正整数颗石子（可以取完整堆，但不能不取）。取走最后一颗石子使其无法操作的一方获胜（即无法操作者输）。假设双方均采取最优策略，判断先手是否存在必胜策略。若先手必胜输出 $1$ ，否则输出 $0$ 。

正解

思路

由于每步只能从序列的最左端或最右端取石子，且石子数高达 $10^9$ ，常规的记忆化搜索或 SG 函数无法直接处理。注意到取石子的位置天然对应着区间收缩，我们考虑从区间博弈的角度切入。

1. 核心观察与状态定义

对于任意连续子序列 $[i, j]$ ，我们考虑在其左侧额外放置一堆石子，使得新序列（包含新增的这堆以及原区间 $[i, j]$ ）成为一个先手必败态（P-position）。

唯一性：如果存在两个不同的石子数 $x_1 < x_2$ 均使得左侧放该数量时为必败态，那么在面对数量为 $x_2$ 的局面时，先手可以直接从该堆中取出 $x_2 - x_1$ 颗石子，将其转移到数量为 $x_1$ 的局面。这意味着先手可以一步将一个必败态转移到另一个必败态，违背了博弈论中必败态的所有后继都是必胜态的基本定理。因此，使局面成为必败态的左侧石子数至多只有一个。
存在性：可以证明这样的石子数必定存在且非负。

基于此，我们定义：

$L[i][j]$ ：在区间 $[i, j]$ 的最左侧添加一堆石子，使得整个新局面为先手必败态时，该堆石子的唯一数量。
$R[i][j]$ ：在区间 $[i, j]$ 的最右侧添加一堆石子，使得整个新局面为先手必败态时，该堆石子的唯一数量。

2. 边界条件

当区间长度为 $1$ 时（即只有单堆 $[i, i]$ ，石子数为 $a_i$ ）：如果在左侧放一堆数量相同的石子 $a_i$ ，局面变成两堆数量相等的石子。后手可以使用对称模仿策略（先手在某一堆取多少，后手就在另一堆取同样多的石子），先手必败。因此：

L[i][i] = R[i][i] = a_i

3. 状态转移推导

考虑如何利用区间 $[i, j-1]$ 的已知信息推导 $L[i][j]$ 。令 $l = L[i][j-1]$ ， $r = R[i][j-1]$ ， $x = a_j$ 。我们需要寻找一个石子数 $L = L[i][j]$ ，使得序列在最左端加上 $L$ 、最右端加上 $x$ 后的局面为必败态。根据 $x$ 与 $l, r$ 的大小关系，分五种情况讨论：

关系条件	$L[i][j]$ 的值	转移逻辑解释
$x = r$	$0$	由 $R[i][j-1] = r$ 的定义，右端本身已有 $r$ 颗石子就已经是必败态，左侧无需石子（ $0$ 颗）。
$x < l$ 且 $x < r$	$x$	左右两端石子数相同。先手无论取哪一端，后手都在另一端取相同数量；任一端被取光后留下的状态均在临界值之内，先手无法反制。
$r < x < l$	$x - 1$	左右两端保持差值 $1$ 。先手取左或取右时，后手可通过对称性或将状态拉回到 $z = r$ 的必败态。
$l < x < r$	$x + 1$	与上述情况对偶，后手可通过将差值抵消或触发必败转移使先手落败。
$x > l$ 且 $x > r$	$x$	当石子数同时超出两侧临界值时，只需保持左右两端石子数相等即可保持对称控制。

同理，推导 $R[i][j]$ 时令 $l = L[i+1][j], r = R[i+1][j], x = a_i$ ：

若 $x = l$ ，则 $R[i][j] = 0$ ；
若 $(x > l \land x > r)$ 或 $(x < l \land x < r)$ ，则 $R[i][j] = x$ ；
若 $l < x < r$ ，则 $R[i][j] = x - 1$ ；
若 $r < x < l$ ，则 $R[i][j] = x + 1$ 。

4. 全局胜负判定

区间递推到区间 $[2, n]$ 后，其左侧使得局面成为必败态所需的石子数为 $L[2][n]$ 。

当 $n = 1$ 时，先手直接取完整堆石子即可获胜，结果为 $1$ 。
当 $n > 1$ 时，原序列最左端的实际石子数为 $a_1$ ：
- 若 $a_1 = L[2][n]$ ，则当前整个局面恰好是先手必败态，先手必输，输出 $0$ ；
- 若 $a_1 \ne L[2][n]$ ，先手必能将第一堆调整至 $L[2][n]$ （若 $a_1 > L[2][n]$ ），或原局面本身是先手必胜态，输出 $1$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def next_end_state(x: int, l: int, r: int, is_left: bool) -> int:
    """根据子区间两侧必败态阈值及新堆石子数推导新端点的必败态阈值。"""
    if x == (r if is_left else l):
        return 0
    if (x > l and x > r) or (x < l and x < r):
        return x
    return x - 1 if (r < x < l if is_left else l < x < r) else x + 1


def is_first_win(piles: list[int]) -> int:
    """判断当前石子序列是否存在先手必胜策略：1 为必胜，0 为必败。"""
    n = len(piles)
    if n == 1:
        return 1

    # L[i][j] 与 R[i][j] 表示给区间加左/右侧石子使其成为必败态所需的石子数
    # 下标 1-based 便于对应原始区间 [i, j]
    l_dp = [[0] * (n + 1) for _ in range(n + 1)]
    r_dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        l_dp[i][i] = r_dp[i][i] = piles[i - 1]

    for length in range(2, n):
        for i in range(1, n - length + 2):
            j = i + length - 1
            l_dp[i][j] = next_end_state(piles[j - 1], l_dp[i][j - 1], r_dp[i][j - 1], is_left=True)
            r_dp[i][j] = next_end_state(piles[i - 1], l_dp[i + 1][j], r_dp[i + 1][j], is_left=False)

    target = next_end_state(piles[n - 1], l_dp[2][n - 1], r_dp[2][n - 1], is_left=True) if n > 2 else piles[n - 1]
    return 0 if piles[0] == target else 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    cases = next(data, 0)

    for _ in range(cases):
        pile_count = next(data)
        stones = [next(data) for _ in range(pile_count)]
        out.append(str(is_first_win(stones)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:40
 * update_at: 2026-10-06 01:40
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 1005;

ll a[MAXN];          // a[i]：第 i 堆石子的数量（下标从 1 开始）
ll Ldp[MAXN][MAXN];  // Ldp[i][j]：在区间 [i,j] 左侧加一堆石子，使整个新局面成为先手必败态所需的石子数
ll Rdp[MAXN][MAXN];  // Rdp[i][j]：在区间 [i,j] 右侧加一堆石子，使整个新局面成为先手必败态所需的石子数

// 在子区间的一端新增石子数为 x 的一堆，求该端对应区间 [i,j] 的必败阈值。
// is_left 为 1：新堆在左端，子区间为 [i,j-1]，l/r 为其两侧阈值；
// is_left 为 0：新堆在右端，子区间为 [i+1,j]，l/r 为其两侧阈值。
// 转移按 x 与两侧阈值 l、r 的大小关系分为五类；注意 x 恰好等于一侧阈值时，
// 取差 1 的临界值而非保持相等，这是本题最容易写错的边界。
ll next_end_state(ll x, ll l, ll r, int is_left) {
    if (is_left) {
        if (x == r) return 0; // 右端本身已是必败态，左侧无需再补石子
    } else {
        if (x == l) return 0; // 左端本身已是必败态，右侧无需再补石子
    }
    // 新堆石子数同时大于或同时小于两侧阈值：保持两端相等即可用对称模仿控制局面
    if ((x < l && x < r) || (x > l && x > r)) return x;
    // 夹在两侧阈值之间：按方向取差 1 的临界值
    if (is_left) {
        if (x >= l && x < r) return x + 1;
        return x - 1;
    } else {
        if (x >= r && x < l) return x + 1;
        return x - 1;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

        if (n == 1) { // 只有一堆时先手直接取完获胜
            printf("1\n");
            continue;
        }

        // 区间长度为 1 时，在任意一侧放上相同数量的石子即为必败态
        for (int i = 1; i <= n; i++) Ldp[i][i] = Rdp[i][i] = a[i];

        // 按区间长度从小到大递推两侧必败阈值
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                Ldp[i][j] = next_end_state(a[j], Ldp[i][j - 1], Rdp[i][j - 1], 1);
                Rdp[i][j] = next_end_state(a[i], Ldp[i + 1][j], Rdp[i + 1][j], 0);
            }
        }

        // 把 a[1] 看作区间 [2,n] 左侧实际存在的堆：若与必败阈值相等则先手必败
        if (a[1] == Ldp[2][n]) printf("0\n");
        else printf("1\n");
    }
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(T \cdot n^2)$ 。状态数为 $\mathcal{O}(n^2)$ ，每个状态的转移仅涉及常数次大小比较与算术运算。对于 $T \leqslant 10, n \leqslant 1000$ ，总计算量约为 $5 \times 10^6$ 次，在时限内非常充裕。
空间复杂度： $\mathcal{O}(n^2)$ 。使用二维数组记录 $L$ 和 $R$ 状态表，空间占用几十兆，满足内存限制。

总结

本题是典型的端点操作类博弈问题。面对极大的单堆石子数和无法直接套用 Nim 结论的限制，突破口在于：

建立基于区间的必败阈值定义（ $L[i][j]$ 和 $R[i][j]$ ），并严格证明该阈值的唯一性与存在性；
将博弈胜负的判定转化为对临界石子数的大力分类讨论，从而在 $\mathcal{O}(n^2)$ 的区间 DP 中完成对博弈态的递推求解。