主题
天平、过河与博弈
概述
这三类题都不适合蛮算。
它们的共同特点是：看懂规则，比埋头计算更重要。
- 天平题看的是“称一次能分出几类”。
- 过河题看的是“谁负责往返最省时间”。
- 博弈题看的是“哪些状态一上手就不该碰”。
只要规则抓对，这三类题并不神秘；
规则抓错，往往算半天都算不出来。
公式速查
| 模型 | 公式 / 结论 | 使用方式 | 对应真题 |
|---|---|---|---|
| 天平称重 | 3^k >= N | 已知异常物一定偏重，求最少称重次数 | 真题1 |
| 过河递推 | f(n)=f(n-2)+min(2a_1+a_{n-1}+a_n,\ a_1+2a_2+a_n) | 每次优先比较“送走最慢两人”的成本 | 真题2 |
| 取石子博弈 | 若每次可取 1~m 枚且取完者胜，则 (m+1) 的倍数是必败态 | 每次把关键数留给对手 | 真题3 |
| 取石子变形 | 若每次可取 1~m 枚且取完者输，则 1 mod (m+1) 是必败态 | 先审清胜负规则再找关键数 | 真题补充4 |
一、天平问题
1. 天平题为什么本质是分类题
2. 基础结论
情况 1：已知异常物一定偏重
情况 2：不知道异常物偏重还是偏轻
3. 天平题的标准思路
4. 经典真题
真题1：9 个外形完全相同的球中有 1 个较重的球，现有一架无砝码天平，至少称几次能保证找出这个较重的球？
选择并提交答案后查看解析
二、过河问题
1. 过河题的本质
2. 经典过桥模型
3. 送走最慢两个人时的两种标准方案
方案 A：让最快的人单独来回送
方案 B：让最前面两位配合送
4. 递推写法
5. 经典真题
真题2：甲、乙、丙、丁四人过桥，单独过桥分别需 1、2、7、10 分钟，每次最多两人同时过桥，两人同行按较慢者计时，且必须有人把手电筒带回。问四人都过桥最少需要多少分钟？
选择并提交答案后查看解析
三、博弈问题
1. 博弈题为什么先找“必败态”
2. 最常见模型：取石子
3. 如果规则改成“取到最后一枚者输”
4. 经典真题
真题3：桌上有 8 枚石子，两人轮流取，每次可取 1 至 3 枚，取到最后一枚者获胜。若双方都采取最优策略，谁能获胜？
选择并提交答案后查看解析
真题补充4：桌上有 10 枚石子，两人轮流取，每次可取 1 至 3 枚，取到最后一枚者输。若双方都采取最优策略，谁能获胜？
选择并提交答案后查看解析