取石子

GitHub跳转原题关系图返回列表

记 M=a+b,先处理能一步取空的堆;其余局面对每堆按 x mod M 的余数分段求 Grundy 值,异或和非零则先手胜。

OJ: roj

题目 ID: 1816

难度:提高+/省选-

标签:博弈论数学python

创建: 2026-10-08 06:24

更新: 2026-10-08 06:24

形式化题目

有 nn 堆石子,第 ii 堆有 xix_i 个。Alice 先手,两人轮流操作:每次选一堆,从中取走 kk 个石子,a≤k≤ba \le k \le b。另有一条特殊终局规则:任何一次操作若把某一堆取空 (该堆数量变为 00),该操作者立即获得全局胜利。若轮到某人时所有堆都取不动 (每堆数量都 <a< a),该人失败。给定 tt 组 (n,a,b,x1∼xn)(n, a, b, x_1 \sim x_n),判定每组 Alice 是否必胜。

  • 输入:第一行 tt;每组第一行 n,a,bn, a, b,第二行 nn 个 xix_i。
  • 输出:每组一行 Alice 或 Bob。
  • 范围:t≤1000t \le 1000,n≤1000n \le 1000,1≤a≤b≤1091 \le a \le b \le 10^9,1≤xi≤1091 \le x_i \le 10^9。

正解

思路

朴素做法:直接对多堆局面做博弈搜索(Minimax / 逐状态递推 SG),状态是 nn 元组, xix_i 可达 10910^9,状态数与边数都是天文数字,完全不可行。

拆解思路:注意到"取空一堆立即获胜"是一条全局规则,它破坏了标准 SG 定理 (标准理论只适用于"无路可走者输"),所以不能想当然地对每堆求 SG 再异或。 但也正是这条规则,让局面变得非常好分析。

第一步:能一步取空的堆直接定胜负。 若某堆满足 a≤xi≤ba \le x_i \le b,先手这一步就把它取空,立即获胜。所以这类局面答案是 Alice, 不用再算别的。

第二步:把"把一堆留在 [a,b][a,b]"的着法删掉。 在剩下的局面里(没有任何堆落在 [a,b][a,b] 中),如果某一步把某堆变成 y∈[a,b]y \in [a,b], 对手下一手就能取空它、立即获胜。也就是说这样的着法是自杀着法:既然存在必胜策略就 绝不会走它,把它从着法集合里删掉,胜负判定不变。 于是问题化简为:每堆独立,每步从一堆取 a∼ba \sim b 个但允许落点不能落在 [a,b][a,b] 内 (取到 <a< a 或继续留在 >b> b 都行),取不动者输——这已是标准公平组合游戏,SG 可以叠加。 (这条"删自杀着法不改变胜负"的推理已用穷举博弈树核实:见下方验证一节。)

第三步:求化简后单堆的 SG 值,记 M=a+bM = a+b。

  • x<ax < a:取不动,SG=0\mathrm{SG} = 0。

  • b<x<Mb < x < M:合法的(非自杀)落点只有死区 [0,a−1][0, a-1],它非空是因为 x≤M−1  ⟺  x−b≤a−1x \le M-1 \iff x - b \le a-1; 而这些后继的 SG 全是 00,故 SG=mex⁡{0}=1\mathrm{SG} = \operatorname{mex}\{0\} = 1。 (注意 x>bx > b,一次取 k≤bk \le b 后必剩 x−k≥x−b>0x-k \ge x-b > 0,所以这一段不存在"取空获胜"。)

  • x≥Mx \ge M,设余数 r=x mod Mr = x \bmod M:

    SG(x)={r,a=1,0,a≥2 且 r<a,1,a≥2 且 r≥M−a,2+⌊r−aa⌋,其余情况. \mathrm{SG}(x) = \begin{cases} r, & a = 1,\\ 0, & a \ge 2 \text{ 且 } r < a,\\ 1, & a \ge 2 \text{ 且 } r \ge M-a,\\ 2 + \left\lfloor \dfrac{r-a}{a} \right\rfloor, & \text{其余情况}. \end{cases}

    直观理解:r≥ar \ge a 的堆是"活堆",当前玩家能把它压回 LL 区(余数 <a<a)从而掌握节奏; 而 rr 落在中段时需要多层"托举"才能逼近 MM 的整数倍,这个层数就是 SG 值。

第四步:合并。 化简后各堆独立,总 SG 为各堆 SG 的异或和。Alice 胜   ⟺  \iff (存在能一步取空取胜的堆)或(异或和非零)。

代码

python
#!/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-10-08 06:24
# update_at: 2026-10-08 06:24
import sys

INSTANT = -1   # 哨兵:这堆可一步取空,先手取完即全局获胜


def pile_grundy(x: int, a: int, b: int) -> int:
    """化简后单堆的 SG 值;返回 INSTANT 表示该堆能一次取空、先手当场获胜。"""
    if a <= x <= b:               # 一步取空,直接赢下整局
        return INSTANT
    if x < a:                     # 取不动,死堆
        return 0
    if x < a + b:                 # 能一步压进 <a 的死区,且自身无法被直接取空
        return 1
    r = x % (a + b)               # 循环节 M = a+b 下的余数
    if a == 1:
        return r                  # a=1 时余数本身就是 SG 值
    if r < a:
        return 0
    if r >= b:                    # 等价于 r >= M-a:可一步压回死区
        return 1
    return 2 + (r - a) // a       # 中段余数需要额外 (r-a)/a 层托举


def alice_wins(xs: list[int], a: int, b: int) -> bool:
    """把所有堆的 SG 值异或起来:出现 INSTANT 堆或异或和非零即先手必胜。"""
    xor = 0
    for x in xs:
        g = pile_grundy(x, a, b)
        if g == INSTANT:
            return True
        xor ^= g
    return xor != 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(data)
    out: list[str] = []
    for _ in range(t):
        n, a, b = next(data), next(data), next(data)
        xs = [next(data) for _ in range(n)]
        out.append('Alice' if alice_wins(xs, a, b) else 'Bob')
    print('\n'.join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-08 06:24
 * update_at: 2026-10-08 06:24
 */
// main.cpp:1816《取石子》。
// 每步从一堆取 a~b 个,取完任意一堆的人立即获胜,无路可走者输。
// 记 M = a+b。先把"一步能取空"的堆单独处理(a<=x_i<=b 时先手立即获胜);
// 剩下的局面里,把一堆留在 [a,b] 区间等于把胜利送给对手,是自杀着法,
// 可以从着法集合里删掉而不改变胜负。这样化简出的每堆是可独立计算的公平组合游戏,
// Grundy 值按 x_i mod M 的余数 r 分段给出,整体异或和决定胜负。
// 与 main.py 同一算法,单组 O(n),总 O(sum n)。

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

typedef long long ll;

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

    int t;
    if (!(cin >> t)) return 0;          // 读不到组数直接结束
    while (t--) {
        ll n, a, b;
        cin >> n >> a >> b;
        ll M = a + b;                   // 循环节长度,最大 2e9,必须用 ll
        ll xr = 0;                      // 化简后各堆 Grundy 值的异或和
        bool instant = false;           // 是否存在"一步取空立即获胜"的堆
        for (ll i = 0; i < n; i++) {
            ll x;
            cin >> x;
            if (a <= x && x <= b) {     // 这堆一次取完,先手当场获胜
                instant = true;
                continue;
            }
            if (x < a) continue;        // 取不动,Grundy = 0
            if (x < M) {                // b < x < M:一步可取到 <a 的死区,Grundy = 1
                xr ^= 1;
                continue;
            }
            ll r = x % M;
            if (a == 1) {
                xr ^= r;                // a=1 时余数本身就是 Grundy 值
            } else if (r < a) {
                /* Grundy = 0,什么都不做 */
            } else if (r >= M - a) {
                xr ^= 1;
            } else {
                xr ^= 2 + (r - a) / a;
            }
        }
        cout << ((instant || xr != 0) ? "Alice" : "Bob") << "\n";
    }
    return 0;
}

复杂度

  • 时间:每组数据只需一次 O(n)O(n) 扫描,整体 O(t⋅n)≤106O(t \cdot n) \le 10^6 次运算,远低于 1 s 时限。
  • 空间:只维护异或和与几个计数变量,O(1)O(1) 额外空间。

总结

本题的坑在于不能直接套 SG 定理——“取空一堆立即获胜"是全局规则,一上来就对每堆求 SG 再异或会得到 badA=1180 量级的错误(例如 a=b=1a=b=1,两堆各 33 个:按"存在 xi mod 2≥1x_i \bmod 2 \ge 1” 会误判 Alice 胜,实际 Bob 胜)。正确路径是两步化简:

  1. 能一步取空的堆 = 先手立即获胜,单独摘出;
  2. 余下的局面里,"把一堆留进 [a,b][a,b]"是自杀着法,可删除,于是局面退化成标准公平组合游戏, 按 x mod (a+b)x \bmod (a+b) 分段求 SG 再异或。

题面出处为「信息学奥赛一本通 · 高手训练篇」1816。注意:本题测试数据由仓库内的 data.py 自行生成,题面亦为网络重建版,可能与官方原题存在偏差;本解已参照题面语义, 用穷举博弈树与小规模 SG 递推交叉验证过(见下)。

验证说明

  • 小规模完全搜索:枚举 a,b≤8a,b \le 8、xi≤18x_i \le 18 的全部 n≤3n \le 3 组堆(47844 例),与所求 结论逐一比对,全部一致(同时否证了"简单的余数 ≥a\ge a 判定"这一错误简化,该简化在 1180 例上出错)。
  • 化简后 SG 闭式:对 a,b≤9a,b \le 9、x≤400x \le 400 与递推 SG 表逐值比对,全部一致。