实验四：一次完整的赛前模拟
本节目标：能限时独立完成省赛难度真题，并讲清所用算法为何正确。
这次要做出什么
前面几课把零件和工具都备齐了：算法族（第 16 到 26 课）、看规模挑算法（第 28 课）、常数优化（第 29 课）、提交前自检（第 30 课）。但考场上不是一题一题分开考的——是在时间压力下连着选题、决策、写码、自检。
这一课不教新算法，做一次完整的赛前模拟。产出两样东西：
- 一份限时解题记录：按省赛节奏（4 小时、5 道题）实际走一遍，记录每道题的读题时间、定下的算法、写完的时刻、自检结果、最终得分。
- 一份讲解稿：对你做出来的每道题，讲清三件事——它为什么可以这么解、复杂度是多少、以及多大的数据规模会把这种方法淘汰掉。
第 2 样是这一课的重点。做出来不等于会做；讲不出「为什么正确」的解法，换一道题你就用不上了。
限时里最先做的判断
一坐下不要打开第一题就写。先花五到八分钟通读全部题目，对每道题做三件事：
- 读数据范围，算出复杂度上限。 这是第 28 课那套：n \le 10^5 就只能上 O(n \log n)，n \le 10^3 才容得下平方级。
- 读问法，缩到两三个算法族。 「让最大值最小」指向二分答案，「第 k 大」指向堆，「方案数」指向动态规划。
- 估自己的完成时间。 这一步最难也最值钱——估错时间的代价比选错算法还大，下一节会量给你看。
这三步做完，你手上就有一张「这五道题分别大概要多久、值多少分」的表。选题顺序就是照着这张表定的。
「估完成时间」有一个必须承认的事实：你的估计一定不准。 所以估计的时候要给自己留余量——估 40 分钟的题按 60 分钟算。下面几节所有数字都是在这个前提下算的。
选题顺序真的决定得分
「选题顺序能有多大影响」听起来是个没法量的问题，但它其实可以建模。把一场比赛抽象成：5 道题，每道题有一个耗时和一个分值，总时长 240 分钟，做完一题才拿分——一题做不完，那题白费，后面的时间也没了。
拿 2000 场随机比赛分别试四种常见的选题顺序：
import random
T = 240
LEVELS = [
('简单甲', 25, 45, 20, 30),
('简单乙', 25, 45, 20, 30),
('中等', 50, 90, 40, 60),
('偏难', 100, 160, 70, 100),
('超难', 150, 400, 80, 130),
]
N = len(LEVELS)
def gen_case(rng):
"""造一场五题的比赛；题面顺序随机打乱，不代表难度顺序。"""
ps = [(rng.randint(t_lo, t_hi), rng.randint(v_lo, v_hi))
for _, t_lo, t_hi, v_lo, v_hi in LEVELS]
rng.shuffle(ps)
return ps
def play(order, case, budget=T):
"""按 order 依次做：做完一题才拿分；一题做不完，那题白费，后面的时间也没了。"""
used = got = 0
done = []
stuck = None
for i in order:
t, v = case[i]
if used + t <= budget:
used += t
got += v
done.append(i)
else:
stuck = (i, t, v, budget - used)
break
return got, used, done, stuck
def best_subset(case, budget=T):
"""枚举所有「时间装得下」的子集，取分值最高的。这一步就是 0/1 背包。"""
best, bsub = -1, None
for mask in range(1 << len(case)):
tt = vv = 0
sub = []
for i in range(len(case)):
if mask >> i & 1:
tt += case[i][0]
vv += case[i][1]
sub.append(i)
if tt <= budget and vv > best:
best, bsub = vv, sub
return best, bsub
STRATS = [
('按题面顺序', lambda c: list(range(N))),
('先易后难（耗时升序）', lambda c: sorted(range(N), key=lambda i: c[i][0])),
('先难后易（分值降序）', lambda c: sorted(range(N), key=lambda i: -c[i][1])),
('性价比（分值/耗时降序）', lambda c: sorted(range(N), key=lambda i: -c[i][1] / c[i][0])),
]
ROUNDS = 2000
rng = random.Random(20260301)
CASES = [gen_case(rng) for _ in range(ROUNDS)]
OPT = [best_subset(c)[0] for c in CASES]
opt_avg = sum(OPT) / ROUNDS
print(f' {ROUNDS} 场模拟比赛：每场 5 题、总时长 {T} 分钟、题面顺序随机打乱')
print(' 选题顺序 平均得分 离上限还差 平均做完几道')
for name, key in STRATS:
tot = done_tot = 0
for c in CASES:
g, _, done, _ = play(key(c), c)
tot += g
done_tot += len(done)
avg = tot / ROUNDS
print(f' {name:<22} {avg:7.1f} {opt_avg - avg:6.1f} {done_tot / ROUNDS:5.2f} 道')
print(f' {"上限（枚举可行的子集）":<22} {opt_avg:7.1f} {0.0:6.1f} '
f'{sum(len(best_subset(c)[1]) for c in CASES) / ROUNDS:5.2f} 道') 2000 场模拟比赛：每场 5 题、总时长 240 分钟、题面顺序随机打乱
选题顺序 平均得分 离上限还差 平均做完几道
按题面顺序 90.6 66.6 1.86 道
先易后难（耗时升序） 109.8 47.4 3.11 道
先难后易（分值降序） 47.6 109.6 0.46 道
性价比（分值/耗时降序） 133.9 23.3 2.93 道
上限（枚举可行的子集） 157.2 0.0 2.91 道同一批题目，只换做题顺序，平均分从 47.6 到 133.9——差 2.8 倍。 这跟算法水平一点关系都没有，纯粹是顺序问题。
两条最值得记住的：
- 「先难后易（按分值挑）」是最差的一种，平均只有 47.6 分，做完 0.46 道。因为分值最高的题往往耗时最长，一道超长题会把 240 分钟全吃掉，后面能做的题一道也碰不到。
- 「按题面顺序」排在倒数第二（90.6 分，只做完 1.86 道）。这最危险，因为它是默认行为——不假思索就从第一题开始写，等价于一个很差的策略。
做完的题数不等于得分
看块 1 的最后两列，有一件事很反直觉：
| 顺序 | 平均得分 | 平均做完几道 |
|---|---|---|
| 先易后难 | 109.8 | 3.11 道 |
| 上限 | 157.2 | 2.91 道 |
「先易后难」做完的题最多，得分却不是最高。 最高分的做法平均少做 0.2 道题，反而多拿 47.4 分。
原因很直接：题目的分值不一样。 三道 30 分的容易题加起来 90 分，还不如一道 100 分的题。你埋头把三道小题做完，看着进度条很满，总分却落后。
所以考场上不要用「做完了几道」来判断自己发挥得好不好——那个指标会把你引向错误策略。
一题做不完的代价
上一节说「一道超长题会把时间全吃掉」。这件事的量级值得单独算：
rng = random.Random(7)
cases = lost = 0
for _ in range(2000):
c = gen_case(rng)
over = [i for i in range(N) if c[i][0] > T]
if not over:
continue
bad = over[0]
g_bad, _, _, _ = play([bad] + [i for i in range(N) if i != bad], c)
g_opt, _ = best_subset(c)
cases += 1
lost += g_opt - g_bad
print(f' {2000} 场里有 {cases} 场存在「单题耗时 > 总时长」的题')
print(f' 这些场次里，先啃那道题比最高分的做法平均少拿 {lost / cases:.1f} 分') 2000 场里有 1243 场存在「单题耗时 > 总时长」的题
这些场次里，先啃那道题比最高分的做法平均少拿 156.4 分2000 场里有 1243 场存在一道「单题就超过总时长」的题——超过六成。也就是说，考场上你大概率会碰到一道做不完的题，这不是小概率事件。
而在这些场次里，先啃它的代价是平均少拿 156.4 分。因为它不只是让你少做一道题，而是让后面所有本来能做的题全部作废——时间已经用光了。
这条对应大纲里的第一个坑：把时间全花在一道难题上。 它的代价不是「少拿那一道题的分数」，而是「整场崩掉」。
判断一道题该不该啃，要在动手之前做。一旦开始写，你会投入十几分钟的沉没成本，那时候再放弃就更难了——这是人都会有的倾向，不靠意志力对抗，靠开工前就把规则定死：比如「超过预计时间 1.5 倍还没写出可运行版本，就立刻跳到下一题」。
选题顺序就是背包
现在来看为什么「性价比排序」还是差上限一截（133.9 对 157.2），以及真正的上限是怎么算出来的。
注意一件事：既然一题做不完就白费，那么你实际完成的题目一定构成一个时间装得下的子集。反过来，任何一个时间装得下的子集，你都能按某个顺序把它全部做完。
所以「选一个做题顺序」本质上就是「选一个时间装得下的题目子集」——而后者正是第 25 课的 0/1 背包：时间是容量，分值是价值，挑一个价值最大又装得下的组合。
拿块 3 那个具体例子验一下：
EX = [(200, 100), (40, 30), (40, 30), (40, 30), (30, 25)]
og, osub = best_subset(EX)
print(f' 五题（耗时, 分值）= {EX}，总时长 {T} 分钟')
print(f' 分值最高的可行子集：第 {osub} 题，共 {og} 分')
for name, key in STRATS:
g, u, done, stuck = play(key(EX), EX)
if stuck:
tag = f'卡在第 {stuck[0]} 题（只差 {stuck[3]} 分钟，那题值 {stuck[2]} 分）'
else:
tag = '时间刚好用尽'
print(f' {name:<22} 得分 {g:>4} 做完 {done} {tag}') 五题（耗时, 分值）= [(200, 100), (40, 30), (40, 30), (40, 30), (30, 25)]，总时长 240 分钟
分值最高的可行子集：第 [0, 1] 题，共 130 分
按题面顺序 得分 130 做完 [0, 1] 卡在第 2 题（只差 0 分钟，那题值 30 分）
先易后难（耗时升序） 得分 115 做完 [4, 1, 2, 3] 卡在第 0 题（只差 90 分钟，那题值 100 分）
先难后易（分值降序） 得分 130 做完 [0, 1] 卡在第 2 题（只差 0 分钟，那题值 30 分）
性价比（分值/耗时降序） 得分 115 做完 [4, 1, 2, 3] 卡在第 0 题（只差 90 分钟，那题值 100 分）这一局最优是 130 分，做法是「做第 0 题和第 1 题」。 注意看这个结局有多紧：200 + 40 = 240，正好把时间用完，一分钟不剩。
而「性价比排序」在这一局只拿 115 分——它按性价比从高到低做，先把三道 30 分的小题和那道 25 分的做完（115 分），轮到第 0 题时只剩 90 分钟，那道题要 200 分钟，只能放弃。它做出了4 道题，却比只做 2 道题的方案少 15 分。
结论：性价比排序是个不错的经验法则（块 1 里它 133.9 分，是四种里最高的），但它不是最优。 差别在于——性价比只看「每一分钟买到多少分」，而背包要看「装得下的组合里哪个总分最高」。前者是贪心，后者才对应问题本身的结构。第 23 课讲过贪心什么时候会失效，这里是同一个道理换了个场景。
考场上你当然不会去枚举 2^5 个子集（虽然五道题真枚举也就 32 种，心算都行）。实用的做法是：按性价比从高到低排，然后检查一遍「排在最后那道题，剩下的时间够不够」。 如果不够，就把它换掉，看看换成别的组合总分会不会更高。五道题的规模，这个检查手算就能做完。
自检时间要算进预算
第 30 课讲过「写对但来不及自检」是常见的失分点。这一课把它算进时间预算里看代价：
def run_check(reserve, p_wrong, seed=31337, rounds=4000):
rng = random.Random(seed)
tot = saved_tot = done_tot = 0
for _ in range(rounds):
c = gen_case(rng)
order = sorted(range(N), key=lambda i: c[i][0])
_, _, done, _ = play(order, c, budget=T - reserve)
done_tot += len(done)
eff = min(1.0, reserve / 30) # 投入越多，救回率越接近上限
got = saved = 0
for i in done:
v = c[i][1]
if rng.random() < p_wrong:
if rng.random() < 0.85 * eff:
got += v
saved += 1
else:
got += v
tot += got
saved_tot += saved
return tot / rounds, saved_tot / rounds, done_tot / rounds
for pw in (0.28, 0.45):
print(f' 假设做出来的题里有 {pw:.0%} 其实是错的，自检最多能救回 85%：')
print(' 预留自检 平均得分 平均救回几道 平均做完几道')
for reserve in (0, 10, 20, 30, 40, 60):
g, s, d = run_check(reserve, pw)
print(f' {reserve:>6} 分 {g:7.1f} {s:6.2f} {d:6.2f}') 假设做出来的题里有 28% 其实是错的，自检最多能救回 85%：
预留自检 平均得分 平均救回几道 平均做完几道
0 分 78.6 0.00 3.10
10 分 82.9 0.24 3.04
20 分 88.8 0.47 3.01
30 分 96.0 0.70 3.00
40 分 95.9 0.70 3.00
60 分 95.9 0.70 3.00
假设做出来的题里有 45% 其实是错的，自检最多能救回 85%：
预留自检 平均得分 平均救回几道 平均做完几道
0 分 60.3 0.00 3.11
10 分 69.9 0.38 3.04
20 分 81.4 0.77 3.01
30 分 93.3 1.14 3.00
40 分 93.2 1.14 3.00
60 分 93.2 1.14 3.00留出 30 分钟自检，平均多做不完 0.1 道题，却多拿 17 到 33 分。
注意曲线的形状：从 0 到 30 分钟一直在涨，30 分钟往后就平了（40 分、60 分都是 96.0）。这是因为模型里自检的收益在 30 分钟就饱和了——再多留只是白白少做题。
所以「自检要留多久」这个问题有实际答案：留到收益饱和的那个点就够，不要预留过多。 具体留多久取决于题目难度和你的出错率，但这个形状是通用的——先陡后平。
怎么算过
这一课的产物是两份材料，判分看四件事：
- 限时是真的限时。 4 小时做完 5 道题，有开始与结束的时间记录。中途可以卡住，但不能停表去查资料、不能事后补做。
- 解题记录完整。 每道题都要记：读题用时、定下的算法与理由（要提到数据范围）、写完的时刻、自检做了什么、最后得了几分、丢分丢在哪。
- 讲解稿讲清三件事。 对做出来的每题：为什么这个方法是对的、复杂度是多少、多大的规模会把它淘汰掉。第三件是重点——说不出这条，说明你只是记住了这道题。
- 至少有一道题是「放弃得对」的。 记录里要能看出你在某道题上做出了放弃的决定，并说清依据（比如「预计耗时超过剩余预算」）。这一条是判断你会不会选题的直接证据。
怎么跑
在 lab 里按这个顺序走：
# 1) 拿题：lab 里给了 5 道省赛难度的题面与样例数据
# 2) 计时开始，4 小时，中途不要停表
# 3) 按你自己的选题顺序做，边做边填解题记录模板
# 4) 时间到，立刻停手（哪怕某题只差一行）
# 5) 用 lab 的判分脚本对答案，算出得分
# 6) 写讲解稿
# 7) 回头复盘：如果换一种选题顺序，这一场能多拿几分？用手算第 7 步是这一课最有价值的一步：你不是在复盘算法，是在复盘决策。
这一课的动手部分落在 lab 里（任务与断言见 lab/0031-lab-04-spaced-repetition-drill/，做完对照 lab/solutions/）。要做的是四件事。
- 先通读、先列表，再动手。 打开五道题，只做第 2 节那三步（读范围、读问法、估时间），把表填出来。这一步不许写代码，15 分钟内完成。
- 定顺序，并写下理由。 照着上一步的表定出做题顺序，写清为什么这么排——要提到「预计耗时」与「分值」两方面。写完就不再改（中途可以放弃某题，但顺序不许重排，这是为了让你看到自己判断的准确度）。
- 限时 4 小时走完。 边做边填记录。卡住超过预计时间 1.5 倍的题，按你自己定的规则放弃，并在记录里写清楚。
- 写讲解稿并复盘。 讲解稿讲三件事（为什么对、复杂度、什么规模会淘汰它）。复盘时算一遍：如果按性价比排序，这一场能多拿几分？ 用手算，不用写程序。
自查清单
- 限时是真的限时，4 小时没停表。
- 五道题都填了记录，包括没做出来的那些（没做出来的也要记：卡在哪、什么时候决定放弃）。
- 每道题的「定下的算法」都写到了数据范围，不只是算法名字。
- 讲解稿的三件事齐全，「什么规模会淘汰它」那一条不能空。
- 至少有一道题记录了「放弃」以及依据。
- 复盘那一步做了，并且算出了「换顺序能多拿几分」。
- 提交前用第 30 课那份清单过了一遍（尤其是格式与调试输出）。
最可能卡在哪
- 一坐下就开始写第一题。 这是「按题面顺序」那个 90.6 分的默认行为。强制自己先通读 15 分钟。
- 估时估得太乐观。 估计值乘 1.5 再填表。宁可高估。
- 舍不得放弃。 已经写了 20 分钟，觉得再撑一下就好了——这正是 156.4 分代价的来源。开工前把放弃规则定死，到点就跳。
- 复盘时只复盘算法。 这一课复盘的是决策：顺序对不对、估时准不准、放弃得对不对。算法错了是第 16 到 26 课的事。
- 讲解稿写成题解。 「先这样再那样」是题解；「为什么这样是对的、什么规模不行」才是讲解稿。
卡壳顺序
- 先确认时间是真的限时。超时了这场模拟就没意义了，重来。
- 顺序定了之后不许重排——这一条是纪律，不是建议。重排了就看不出你的判断准不准。
- 某道题卡住，先看是不是数据范围读错了（第 28 课那套）。范围读错会导致算法选错，那是根本性的。
- 算法选对了但写不出来，看是不是边界没想清。用小数据手推一遍，别硬想。
- 到了放弃规则触发的时间点，立刻跳。跳之前把记录填完，别等到最后凭记忆补。
- 讲解稿写不下去，说明那道题你其实没真懂——回课件对应那一课重看。
做完之后
这一场模拟的结果不是分数，是一份关于你自己的数据：
- 估时准确度：你预计的和实际用的差多少？如果系统性偏低，下次乘的系数要调大。
- 选题判断：如果按性价比重排能多拿多少分？差得多说明你的直觉顺序需要改。
- 放弃果断度：有没有在该跳的时候没跳？
- 讲解稿的完成度：哪些题你能讲清「什么规模会淘汰它」，哪些讲不出？
把这份数据带到第 33 课的综合实战里去——那一课是这套流程的最后一次完整演练。