BISHI34　甜蜜的博弈¶

简单通过率 44.09%python3样例通过牛客 AC

讲解章节：博弈论

一句话

每次可取 1；k 为偶数时可取 2；k 为 5 的倍数时可取 5。

解题思路¶

这题考什么¶

公平组合游戏的必败态找规律。先打小表（k=0 为必败，因为无法行动）：

k : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
态: L W W L W W L W W L  W  L  W  L  W  L  W  L  W  L  W

必败态集合 = {0, 3, 6} ∪ {大于等于 9 的奇数}。

证明（k >= 7 部分）：

偶数 k >= 8 必胜：k = 8 时取 2 到 6（必败）；k >= 10 时取 1 到达奇数 k-1 >= 9（必败）。
奇数 k >= 9 必败：k 是奇数，2 不整除 k，所以只能取 1 或（当 5 | k 时）取 5。取 1 到 k-1（偶数且 >= 8，必胜）；取 5 到 k-5（偶数且 >= 10 时必胜，k=15 时到 10 也必胜）。所有后继都是必胜态，故本身必败。

前面 0..8 的零散值按小表直接特判。

数据规模与复杂度¶

T <= 100，N <= 1e9。找出规律后每组 O(1) 判定。若不总结规律而直接对每个 k 递推必败态，要开 1e9 的表，时间和内存都不可行，所以必须先把小表上的规律证成闭式再套用。博弈论中必胜态与必败态的定义和分析见 50-博弈论。

坑在哪¶

「无法取走钻石的人输」，k = 0 时无法行动 —— 这是必败态的定义，但 N >= 1 所以先手永远至少能取 1 颗；
别漏掉 3 和 6 这两个「小奇点」，只写「奇数且 >= 9」会 WA 掉 N = 3 （样例第二组就是 3）；
取 5 的条件是 5 | k 并且 k >= 5，取 2 同理；k=5 时取 5 到 0 必胜，这正是 5 与 15/25 结论不同的原因。
5201314 是偶数且不在 {0,6} 里，先手必胜 -> Alice，样例第三组。

参考实现¶

solutions/BISHI34.py
import sys

LOSE_SMALL = {0, 3, 6}                 # 9 以下的必败态（0/3/6）


def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(1, t + 1):
        n = int(data[i])                   # 每组只有一个数，token 下标与组号一一对应
        # 必败态：0、3、6，或者 >=9 的奇数
        lose = n in LOSE_SMALL or (n >= 9 and n % 2 == 1)
        out.append("Bob" if lose else "Alice")
    sys.stdout.write("\n".join(out) + "\n")


main()

BISHI34 甜蜜的博弈¶