记 M=a+b,先处理能一步取空的堆;其余局面对每堆按 x mod M 的余数分段求 Grundy 值,异或和非零则先手胜。
OJ: roj
题目 ID: 1816
难度:提高+/省选-
标签:博弈论数学python
创建: 2026-10-08 06:24
更新: 2026-10-08 06:24
形式化题目
有
- 输入:第一行
;每组第一行 ,第二行 个 。 - 输出:每组一行
Alice或Bob。 - 范围:
, , , 。
正解
思路
朴素做法:直接对多堆局面做博弈搜索(Minimax / 逐状态递推 SG),状态是
拆解思路:注意到"取空一堆立即获胜"是一条全局规则,它破坏了标准 SG 定理 (标准理论只适用于"无路可走者输"),所以不能想当然地对每堆求 SG 再异或。 但也正是这条规则,让局面变得非常好分析。
第一步:能一步取空的堆直接定胜负。
若某堆满足
第二步:把"把一堆留在
第三步:求化简后单堆的 SG 值,记
-
:取不动, 。 -
:合法的(非自杀)落点只有死区 ,它非空是因为 ; 而这些后继的 SG 全是 ,故 。 (注意 ,一次取 后必剩 ,所以这一段不存在"取空获胜"。) -
,设余数 : 直观理解:
的堆是"活堆",当前玩家能把它压回 区(余数 )从而掌握节奏; 而 落在中段时需要多层"托举"才能逼近 的整数倍,这个层数就是 SG 值。
第四步:合并。 化简后各堆独立,总 SG 为各堆 SG 的异或和。Alice 胜
代码
#!/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()/**
* 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;
}复杂度
- 时间:每组数据只需一次
扫描,整体 次运算,远低于 1 s 时限。 - 空间:只维护异或和与几个计数变量,
额外空间。
总结
本题的坑在于不能直接套 SG 定理——“取空一堆立即获胜"是全局规则,一上来就对每堆求 SG
再异或会得到 badA=1180 量级的错误(例如
- 能一步取空的堆 = 先手立即获胜,单独摘出;
- 余下的局面里,"把一堆留进
"是自杀着法,可删除,于是局面退化成标准公平组合游戏, 按 分段求 SG 再异或。
题面出处为「信息学奥赛一本通 · 高手训练篇」1816。注意:本题测试数据由仓库内的
data.py 自行生成,题面亦为网络重建版,可能与官方原题存在偏差;本解已参照题面语义,
用穷举博弈树与小规模 SG 递推交叉验证过(见下)。
验证说明
- 小规模完全搜索:枚举
、 的全部 组堆(47844 例),与所求 结论逐一比对,全部一致(同时否证了"简单的余数 判定"这一错误简化,该简化在 1180 例上出错)。 - 化简后 SG 闭式:对
、 与递推 SG 表逐值比对,全部一致。