Cheat Sheet速查表
跳转到主要内容

数学游戏与博弈策略速查表

先辨规则与条件，再选方法：组合博弈找必败态，策略博弈找均衡，概率题明确样本空间，数字谜题用枚举、递推与搜索。以下取石子游戏均采用取走最后一个者获胜的规则。

算法复杂度速查 · Python 3 速查

公平组合博弈

双方在同一局面拥有相同的合法着法。“必败态”指轮到行动的一方在对手最优应对时必败。

尼姆游戏

Nim 异或判定

三堆 3、4、5 个，把第一堆取成 1，异或和变为 0

x1⊕x2⊕⋯⊕xn=0x_1\oplus x_2\oplus\cdots\oplus x_n=0

规则：每次只从一堆取任意正数，可取完整堆。

策略：异或和为 0 是必败态。非零时，把某堆 x 减至 x⊕s，使总异或和归零。

例子：3⊕4⊕5=2；首手从 3 取走 2，留下 1⊕4⊕5=0。

取最后一个者负的反尼姆，需要另判终局。

展开原理

从异或和为 0 的局面出发，任何合法行动都会使它非零；从非零局面出发，总能减小某一堆，使异或和归零。因此，每次把 0 留给对手，就能保持优势。s 表示当前所有堆数量的异或和。

巴什博弈

Bash Game 凑固定和

每次取 1 到 4 个，5 的倍数是必败态；32 可先取 2

n≡0(modm+1)n\equiv0\pmod{m+1}

规则：一堆 n 个，每次取 1～m 个。

策略：m+1 的倍数是必败态。首手取余数，此后对手取 k，你取 m+1−k。

例子：每次取 1～4 个时，30 个先手必败；32 个先取 2。

允许取数必须连续为 1～m，离散取数集合需重新分析。

展开原理

对手取 k 个，你取 m+1−k 个，两手总共取 m+1 个，局面按固定周期递减。从 m+1 的倍数出发，无论取多少都会离开这个集合；从其他局面则可一步回到集合。

威佐夫博弈

Wythoff's Game 黄金分割

威佐夫必败对为 1,2；3,5；4,7；6,10；8,13

(ak,bk)=(⌊kφ⌋,⌊kφ2⌋)(a_k,b_k)=(\lfloor k\varphi\rfloor,\lfloor k\varphi^2\rfloor)

规则：从一堆任取，或两堆同时取相同正数。

判定：两堆排序为 a≤b，令 k=b−a；若 a=⌊kφ⌋，就是必败态。φ=(1+√5)/2。

例子：(1,2)、(3,5)、(4,7)、(6,10)、(8,13) 都是必败对。

含终局 (0,0)。准确位置由取整公式决定，不是斜线上的所有点。

展开原理

两列黄金分割取整数列互补，并且 bₖ−aₖ=k。必败对之间不能一步互达，其他局面总能一步到达某个必败对。例如 (2,3) 可把第二堆减为 1，得到排序后的 (1,2)。

斐波那契尼姆

Fibonacci Nim Zeckendorf 分解

20 分解为 13 加 5 加 2，首手取最小项 2

r≥z(n)⟹take z(n)r\ge z(n)\Longrightarrow\text{take }z(n)

规则：首手不能取完；之后每次最多取对手上一手的 2 倍。

策略：将 n 分解为不相邻斐波那契数之和，记最小项为 z(n)。当前上限 r≥z(n) 时可取最小项制胜，否则必败。

例子：20=13+5+2，首手取 2；初始 n 本身为斐波那契数时先手必败。

不仅要看剩余 n，还要看当前允许取数的上限 r。

展开原理

每个正整数都能唯一分解为不相邻的斐波那契数之和。可用贪心法反复取“不超过剩余值的最大斐波那契数”，最后一项就是 z(n)。首手上限为 n−1；若 n 本身是斐波那契数，z(n)=n，首手便无法取到制胜项。

Sprague–Grundy 定理

SG Theorem mex 与异或

后继值 0 和 1 的 mex 为 2；独立子游戏 SG 值 3 和 5 异或为 6

g(G+H)=g(G)⊕g(H)g(G+H)=g(G)\oplus g(H)

计算：当前 SG 值是全部后继 SG 值的 mex，即未出现的最小非负整数；终局值为 0。

策略：独立子游戏的 SG 值按位异或；总值为 0 是必败态，非零时设法一步变为 0。

例子：mex{0,1,3}=2；两个子游戏值为 3、5，总值 3⊕5=6。

适用于正常玩法、无无限对局的公平游戏；每回合只动一个子游戏。

展开原理

SG 值由全部合法后继的值决定。没有后继时 mex∅=0；例如后继值为 {0,1,3}，当前值就是 2。普通尼姆的一堆 n 个石子满足 g(n)=n，其他游戏不能直接用物品数量代替 SG 值。

g(G)=mex⁡{g(H):G→H}g(G)=\operatorname{mex}\{g(H):G\to H\}

巧克力博弈

Chomp 策略窃取

左下角有毒，选择一格后吃掉它与右上方全部格子

mn>1⟹first player winsm n>1\Longrightarrow\text{first player wins}

规则：毒格在左下角；选一格，吃掉它及其右上方矩形，吃毒格者负。

结论：除 1×1 外，矩形初始棋盘先手存在必胜策略，可用策略窃取证明。

边界：存在性证明不直接给出一般棋盘的制胜首手。

只吃右上角一格是证明的起点，不是所有棋盘的通用制胜着法。

展开原理

先手先只吃右上角一格。若这一手能赢，结论成立；否则后手存在制胜回应。但先手本可在第一手直接走这个回应，得到同一局面，再采用原本后手的制胜策略，产生矛盾。这个证明说明必胜策略存在，却没有构造通用的制胜首手。

策略博弈

纳什均衡：其他人的策略不变时，任何人单独改变策略都无法提高自己的收益。

囚徒困境

Prisoner's Dilemma 占优策略

双方合作各得 3，双方背叛的均衡各得 1

T>R>P>ST>R>P>S

收益顺序为（自己，对手）。

自己 ＼ 对手合作背叛
合作(3,3)(0,5)
背叛(5,0)(1,1)

结论：无论对手怎样选，背叛都更有利；唯一纳什均衡是双方背叛。

要点：均衡 (1,1) 比共同合作 (3,3) 更差，个体最优未必带来集体最优。

展开原理

对手合作时，自己背叛得 5，比合作的 3 高；对手背叛时，自己背叛得 1，比合作的 0 高。因此背叛是严格占优策略。常见模型还加上 2R>T+S，表示共同合作比轮流占对方便宜的平均收益更高。

石头剪刀布

Rock–Paper–Scissors 混合策略

石头胜剪刀，剪刀胜布，布胜石头，均衡概率各三分之一

(pR,pS,pP)=(13,13,13)(p_{\mathrm R},p_{\mathrm S},p_{\mathrm P})=(\tfrac13,\tfrac13,\tfrac13)

规则：同时出手，石克剪、剪克布、布克石。

策略：赢 +1、输 −1、平 0 时，各以 1/3 概率随机出手，期望收益为 0；无纯策略均衡。

收益不对称时，均衡概率需要重新计算；等概率结论针对标准对称收益。

展开原理

任何一种固定手势都有能击败它的最佳回应，因此不存在纯策略均衡。在标准对称收益下，等概率出三种手势，让对手选择任何手势的期望收益都为 0。

海盗分金

Pirate Game 逆向归纳

五人分 100 枚金币，依次分得 98、0、1、0、1

(98, 0, 1, 0, 1)(98,\ 0,\ 1,\ 0,\ 1)

规则：5 人分 100 枚金币，依次提案；赞成票至少半数则通过，否则提案人出局。

策略：从末轮倒推。1 号自己投赞成，再给 3、5 号各 1 枚，比他们下一轮的 0 更好。

含提案人投票；偏好依次为生存、金币，同收益时否决。改为严格过半需重新倒推。

展开原理

从只剩 4、5 号开始倒推：4 号靠自己的一票即可拿走 100。剩 3 人时，3 号给 5 号 1 枚即可通过；剩 4 人时，2 号给 4 号 1 枚即可通过。因此轮到 1 号时，3、5 号在下一轮都会得 0，各给他们 1 枚即可买到两票。

蜈蚣博弈

Centipede Game 从终点倒推

四轮停止收益为 2,0；1,4；8,2；4,16，最后继续为 32,8

stop at round 1\text{stop at round 1}

规则：轮流决定终止或继续；继续可增加总收益，并把决定权交给对手。

结论：图中末轮 B 选 16 而不是 8；逐轮倒推，得到首轮 A 停止的均衡。

依赖有限已知终点、给定收益与理性为共同知识；改变前提后应重新推导。

展开原理

括号内依次是 A、B 的收益。最后一轮 B 选停止得 16，优于继续后的 8；A 预见此结果，上一轮选停止得 8，优于继续后的 4。再向前推，B 选 4 而非 2，A 选 2 而非 1，因此首轮停止。

重复囚徒困境

Infinitely Repeated PD 未来惩罚

一直合作每轮得 3；背叛一次得 5，此后永久惩罚每轮得 1

δ≥T−RT−P\delta\ge\frac{T-R}{T-P}

策略：无限重复时，双方先合作；一旦出现背叛，之后永久背叛，即 Grim Trigger。

判定：持续合作的折现收益不少于单次背叛后接受惩罚的收益时，合作可维持。

例子：T=5、R=3、P=1 时，δ≥1/2。

以牙还牙 Tit for Tat 只复制上一轮行动，需另算条件；有限已知轮数也不能直接套用。

展开原理

持续合作的折现收益为 R/(1−δ)；背叛当轮拿到 T，此后每轮拿到 P。比较两者得到合作阈值。惩罚阶段的双方背叛本身是单次博弈的均衡，因此惩罚可信；阈值等号处表示两种选择收益相同。

R1−δ≥T+δP1−δ\frac{R}{1-\delta}\ge T+\frac{\delta P}{1-\delta}

斗鸡博弈

Chicken Game 两个纯策略均衡

对手转向时直行，对手直行时转向，对应两个纯策略均衡

(S,G),(G,S)(S,G),\quad(G,S)

收益顺序为（自己，对手）。

自己 ＼ 对手转向 S直行 G
转向 S(0,0)(−1,+1)
直行 G(+1,−1)(−10,−10)

结论：一方转向、另一方直行，是两个纯策略均衡；双方直行的结果最差。

补充：本组收益还有混合均衡：各以 1/10 概率直行。

能改变对方预期的是可信且可观察的承诺，口头宣称不会自动改变行动空间。

展开原理

对手转向时，自己直行得 +1，高于转向的 0；对手直行时，自己转向得 −1，高于直行的 −10。若对手直行概率为 q，自己直行的期望收益为 1−11q，转向为 −q；令两者相等，得到混合均衡 q=1/10。

概率与统计

概率结论依赖样本空间、抽样方式和信息获取机制。先明确条件，再计算条件概率或期望。

蒙提霍尔问题

Monty Hall 开门规则决定概率

初选一号门，车在一号时换门输，车在二号或三号时换门赢，三种情况等可能

P(switch)=23,P(stay)=13P(\mathrm{switch})=\frac23,\quad P(\mathrm{stay})=\frac13

条件：三扇门后等概率放一辆车、两只羊。主持人知道车在哪，总打开一扇未选的羊门，且总允许换门。

结论：坚持原门赢的概率为 1/3；始终换门赢的概率为 2/3。

判断：换门获胜恰好等于“第一次选错”，该事件的概率就是 2/3。

主持人随机开门、可能开出车，或只在特定情况下让你换门时，必须重新建模。

展开原理

固定初选 1 号门，按车的位置分三种等概率情况：车在 1 号时换门输；车在 2、3 号时，主持人必须打开另一扇羊门，换门都赢。这里比较的是始终换门的总体胜率。若额外条件是“主持人恰好打开指定门”，还需明确主持人有多个羊门可选时的开门规则。

生日悖论

Birthday Problem 先算全部不同

至少两人同生日的概率曲线，23 人约百分之50.7，50 人约百分之97.0，70 人约百分之99.9

P=1−∏k=0n−1(1−k365)P=1-\prod_{k=0}^{n-1}\left(1-\frac{k}{365}\right)

条件：生日相互独立，在 365 天上均匀分布，忽略闰日。问题是任意两人同生日。

结论：23 人时概率约 50.7%；50 人约 97.0%；70 人约 99.9%。

方法：先计算所有人生日都不同的概率，再用 1 减去它。

公式适用于 n≤365；n≥366 时概率为 1。“有人与你同生日”是另一个问题。

展开原理

第 1 人生日任意，第 2 人避开已有日期的概率为 364/365，第 3 人为 363/365，依次相乘。23 人共有 253 对可比较，配对数按平方量级增长；不同配对的撞生日事件并不相互独立。

P≈1−e−n(n−1)/(2×365)P\approx1-e^{-n(n-1)/(2\times365)}

散列到 M 个等可能桶时，出现碰撞所需的样本规模也是平方根量级。

男孩女孩悖论

Boy or Girl 先说明如何得知

两孩按长幼有 BB、BG、GB、GG 四种等概率情况，按至少一个男孩筛选后排除 GG，BB 占剩余三种的三分之一

P(BB∣{BB,BG,GB})=13P(BB\mid\{BB,BG,GB\})=\frac13

条件：理想模型中两孩性别独立，男孩女孩各 1/2；随机抽取两孩家庭，再筛选“至少一个男孩”。

结论：按长幼顺序，剩下 BB、BG、GB 三种等概率情况，两人都是男孩的概率为 1/3。

变体：若已知老大是男孩，答案为 1/2；若随机观察一名孩子，看到男孩，另一名是男孩也为 1/2。

“至少一个是男孩”这句话本身不足以确定抽样机制，问法和信息获取方式都要写清。

展开原理

按家庭筛选时，BB、BG、GB、GG 各占 1/4，排除 GG 后 BB 占 1/3。随机观察一名孩子则不同：BB 家庭必然让你看到男孩，BG、GB 只有一半机会，因此观察到男孩后，BB 的权重变为 1/2。

疾病检测与假阳性

Base Rate & Bayes 基准率与后验概率

假设一万人中患病100人：99真阳性、1假阴性；健康9900人：495假阳性、9405真阴性；阳性中真病比例为六分之一

P(D∣+)=9999+495=16P(D\mid +)=\frac{99}{99+495}=\frac16

假设参数：患病率 1%，灵敏度 99%，假阳性率 5%。

按万人计：患病 100 人中 99 人阳性；健康 9,900 人中 495 人阳性。

结论：全部 594 名阳性者中有 99 名患病，后验概率为 1/6，约 16.7%。

灵敏度是“已患病者检出阳性的概率”，不能直接当成“阳性者患病的概率”。

展开原理

令 p 为患病率、s 为灵敏度、f 为假阳性率，阳性可能来自真阳性或假阳性两条路径：

P(D∣+)=spsp+f(1−p)P(D\mid +)=\frac{s p}{s p+f(1-p)}

上面的数字是用于计算条件概率的假设例子。分母必须包含来自健康人群的假阳性，不能只看检出率。

圣彼得堡悖论

St. Petersburg Paradox 期望值与效用

第 k 次首次正面的奖金为二的 k 次方、概率为二的负 k 次方，每一项对期望的贡献都是一，级数发散

E[X]=∑k=1∞2k2−k=∞\mathbb E[X]=\sum_{k=1}^{\infty}2^k2^{-k}=\infty

规则：反复抛公平硬币，首次正面出现在第 k 次时，奖金为 2 的 k 次方。

结论：每种结果对期望的贡献都为 1，因此理想模型中的数学期望无穷大。

理解：期望奖金与期望效用是不同的评价。只对奖金取对数时，确定性等价为 4。

“4”依赖特定效用模型；考虑初始财富、入场费或兑奖上限后，不能把它当成通用票价。

展开原理

首次正面恰在第 k 次的概率为 2 的负 k 次方。若采用 u(X)=ln X，只评价奖金本身，则：

E[ln⁡X]=2ln⁡2,CE=e2ln⁡2=4\mathbb E[\ln X]=2\ln2,\qquad \mathrm{CE}=e^{2\ln2}=4

实际把效用施加在最终财富上时，还需要指定初始财富和费用；有限的最高奖金也会改变数学期望。

辛普森悖论

Simpson's Paradox 分组权重反转

A 在简单组80%高于B的70%，困难组20%高于B的10%，合并后A约22.9%却低于B约68.8%，因为样本权重不同

pA,i>pB,i ⇏ pˉA>pˉBp_{A,i}>p_{B,i}\ \not\Rightarrow\ \bar p_A>\bar p_B

现象：A 在每个分组中的成功率都高于 B，合并后却可能低于 B。

分组A 成功 / 总数B 成功 / 总数
简单组4/5 = 80%350/500 = 70%
困难组20/100 = 20%1/10 = 10%
合并24/105 ≈ 22.9%351/510 ≈ 68.8%

核查分组与权重，也要结合抽样设计和因果关系；不能机械认定分组结果总比总体结果更真实。

展开原理

合并成功率是各组成功率的加权平均。A 有 100/105 的样本来自困难组，B 有 500/510 来自简单组，两组采用了不同权重，因此总体排序可以反转。若对 A、B 使用完全相同的非负分组权重，每组都较高的一方在加权后仍会较高。

数字谜题与搜索

先固定允许的运算与动作，再选择枚举、同余、递推、二分或最优停止。

24 点

24 Game 穷举表达式树

3、3、8、8 四个数各用一次，八除以三减八除以三得到二十四，中间分母是三分之一

8÷(3−8÷3)=248\div(3-8\div3)=24

规则：四个数各用一次，使用加、减、乘、除和括号，目标为 24；中间可出现分数或负数。

方法：反复选择两个数合并为一个结果，递归搜索；减法、除法要考虑两个顺序，除数不能为 0。

例子：3、3、8、8 可组成 8÷(3−8÷3)=24。

使用有理数精确运算，避免浮点误差；不要只搜索一种括号结构。

展开原理

四个操作数共有 5 种二叉括号结构。未去重的枚举上界为 4!×4³×5=7,680，包含重复式和除零等无效式。

将牌面记为 1～13、忽略花色、允许重复，四数多重集合共有 1,820 种。在仅用四则运算和括号的规则下，以有理数穷举可得 1,362 种有解、458 种无解；这些组合在真实抽牌中并不等概率。

韩信点兵与中国剩余定理

Chinese Remainder Theorem 同余方程组

人数除三余二、除五余三、除七余二，构造二乘七十加三乘二十一加二乘十五等于二百三十三，模一百零五得到二十三

x≡23(mod105)x\equiv23\pmod{105}

问题：人数除以 3 余 2、除以 5 余 3、除以 7 余 2，求最小正整数解。

结论：最小正解为 23；全部整数解为 23+105k，其中 k 为整数。

原理：模数两两互质时，同余方程组在模数乘积的意义下有唯一解。

模数必须为正；若不互质，需先检查余数在各公因子模下是否兼容。

展开原理

70 在模 3 下等于 1，在模 5、7 下等于 0；21 对模 5 起同样作用；15 对模 7 起同样作用。因此 2×70+3×21+2×15=233 满足全部条件，减去两倍 105 得到 23。模数不互质但条件兼容时，解的周期改为模数的最小公倍数。

约瑟夫环

Josephus Problem 递推与编号

41 人从1号开始报数，报到2出局，最终幸存者19；41等于32加9，幸存者为二乘九加一

J(n,2)=2(n−2⌊log⁡2n⌋)+1J(n,2)=2\left(n-2^{\lfloor\log_2n\rfloor}\right)+1

规则：n 人编号 1～n 围成一圈，从 1 号开始报 1，报到 k 者出局，下一人重新报 1。

结论：k=2 时有上面的闭式；41=32+9，因此幸存者为 2×9+1=19。

通用方法：逐步从 1 人递推到 n 人即可求任意 k 的幸存编号。

先约定从谁开始、如何报数，以及编号从 0 还是 1 起；不同约定会改变结果。

展开原理

使用从 1 开始的编号，递推关系为：

J(1,k)=1,J(n,k)=((J(n−1,k)+k−1) mod n)+1J(1,k)=1,\quad J(n,k)=((J(n-1,k)+k-1)\bmod n)+1

若使用从 0 开始的编号，则初值为 0，每轮对“上一轮结果加 k”取模。k=2 时，也可将 n 的二进制最高位 1 移到末尾；41 的 101001₂ 变为 010011₂，即 19。

猜数字与二分

Binary Search 一问一比特

候选数量从1000逐次减到500、250、125、63，持续二分，最多十个是非问题可确定一个数

qmin⁡=⌈log⁡2N⌉q_{\min}=\lceil\log_2N\rceil

问题：秘密整数在 1～N 中，每次可问一个答案可靠的是非问题。

策略：询问“是否大于当前区间中点”，每次将候选范围尽量减半。

结论：最坏至少需要向上取整的 log₂N 问，二分可达到此下界；1～1,000 只需 10 问。

这里计算的是二元问答次数。允许的回答类型或存在回答错误时，模型和界限会改变。

展开原理

q 个二元答案最多区分 2 的 q 次方种情况；要区分 N 个整数，必须满足 2^q≥N。二分将两条分支的候选数量尽量平衡，因而达到这一最坏情况的下界。这也给出了 1 比特信息的直观含义。

秘书问题

Secretary Problem 最优停止

大样本下，跳过前约百分之36.8后选择第一个刷新纪录者，选中全场最佳的概率也趋近百分之36.8

rn→1e,Pn⋆→1e\frac{r}{n}\to\frac1e,\qquad P_n^\star\to\frac1e

条件：总人数 n 已知、到达顺序随机、能力无并列；只能比较已见者的相对名次，每次取舍不可撤回，目标是选到全体最佳。

策略：先跳过前 r 人并记住最高水平，之后选第一个超过此前所有人的候选人；若始终没有，则选最后一人。

结论：n 很大时 r 约为 n/e，成功率趋于 1/e≈36.8%；n=10 时最优跳过 3 人，成功率约 39.9%。

37% 是渐近规则；未知总数、可回头或收益目标不同的找房等场景，不能直接套用。

展开原理

若最佳者出现在第 k 位，策略成功的条件是前 k−1 人中的最佳者落在最初跳过的 r 人中。对最佳者的位置求和，可得有限 n 下的成功率：

Pn(r)=rn∑j=rn−11j,1≤r<nP_n(r)=\frac rn\sum_{j=r}^{n-1}\frac1j,\quad1\le r<n

对整数 r 逐一求最大值即可，不必强行向下取整 n/e。大样本令 x=r/n，成功率近似为 −x ln x，在 x=1/e 处达到最大。

水罐问题

Water Jug 最大公因数与搜索

3升和5升空桶经过装满、互倒、倒空六步，从0,0依次到0,5、3,2、0,2、2,0、2,5、3,4，在5升桶内得到4升

gcd⁡(a,b)∣c,0≤c≤max⁡(a,b)\gcd(a,b)\mid c,\quad0\le c\le\max(a,b)

规则：容量 a、b 为正整数，两桶初始为空；可装满、倒空，或互倒至源桶空或目标桶满，水源充足。

判定：要在其中一桶量出 c 升，必须且只需满足 gcd(a,b) 整除 c，且 c 不超过较大桶容量。

例子：3 升、5 升桶量 4 升，最短可用 6 步；图中状态按（3 升桶，5 升桶）记。

若目标改为“两桶合计 c 升”，或不能倒掉水，就要重新定义目标和合法动作。

展开原理

合法动作始终保持两桶水量为 gcd(a,b) 的整数倍，因此整除条件是必要的；贝祖定理及反复互倒给出可达性。求最少步骤时，把状态 (x,y) 看作图上的节点，以一次装满、倒空或互倒为一条边，从 (0,0) 做广度优先搜索；等成本边的 BFS 会给出最短方案。

常用符号

符号快速解释
⊕按位异或，不是普通加法
mex未出现的最小非负整数，如 mex{0,1,3}=2
⌊x⌋、φ向下取整；黄金分割数 φ=(1+√5)/2
T、R、P、S单方背叛、共同合作、共同背叛、单方合作的收益
δ未来收益的折现因子，0≤δ<1
P(A∣B)已知 B 成立时 A 的条件概率
E[X]、CE随机变量的期望；给定效用模型下的确定性等价
gcd(a,b)a、b 的最大公因数
x≡a (mod m)x 除以 m 的余数与 a 相同
e自然对数的底，约 2.71828

先检查这六件事

  • 胜负规则：最后行动者胜还是负？
  • 行动限制：每回合能动几堆、取多少，是否受上一手影响？
  • 信息与顺序：同时还是轮流，终点是否已知？
  • 收益与偏好：金币、存活、投票门槛和惩罚方式是否写明？
  • 概率模型：随机顺序、独立、均匀、基准率和信息获取方式是否成立？
  • 搜索目标：求任意解、最短方案，还是最大化选中最佳者的概率？

计算与实现

任务实现方法关键条件
尼姆判定与制胜手对各堆异或，再扫描一遍寻找可减小的堆固定字长整数下，时间 O(堆数)，额外空间 O(1)
巴什判定求 n 除以 m+1 的余数允许取数恰为连续的 1～m
威佐夫判定排序，求差 k，再计算 ⌊kφ⌋大整数应避免浮点舍入误差
斐波那契尼姆贪心求不相邻斐波那契分解的最小项同时记录本回合的取数上限
一般有限 SG 游戏把局面看作无环图，记忆化计算后继的 mex实际开销由状态数、后继数和 mex 的实现决定
生日概率顺序累乘“全部不同”的概率，再取补集n≤365 时 O(n)；更大 n 直接为 1
24 点选两数合并并递归，或枚举 5 种括号结构用有理数处理分数和除零；可按状态去重
中国剩余定理扩展欧几里得求逆元并合并同余式互质用乘积周期；非互质先检验兼容性
约瑟夫环幸存者一维递推通用 O(n) 时间、O(1) 额外空间，不必模拟完整圈
猜数字维护闭区间，每问剔除约一半候选O(log N) 个可靠的二元问题
秘书问题阈值反向累计调和和，比较各个整数 rO(n) 时间；n 很大时使用约 n/e 的近似
两桶最短量水方案对整数状态 (x,y) 做 BFS状态数至多 (a+1)(b+1)，动作成本必须相同

参考与延伸阅读

分类:科学与学习
标签: 数学博弈论组合博弈策略博弈Nim纳什均衡算法概率统计数论搜索速查表