# 实验四 · 一次完整的赛前模拟（参考解）

> 这一份对应 `../0031-lab-04-spaced-repetition-drill/` 那一场模拟的**赛后**：
> 五道题的参考解、一份填好的记录、一份填好的讲解稿。
> **学生先做完再来看这里。**

---

## 一、这一场的结果

| 题 | 参考解 | 得分 | 用时 | 结果 |
| --- | --- | --- | --- | --- |
| p1 舞台高度 | `reference/p1.py` | 30 / 30 | 28 分钟 | 拿满 |
| p5 雨天迷宫 | `reference/p5.py` | 80 / 80 | 35 分钟 | 拿满 |
| p2 四边形合并 | `reference/p2.py` | 60 / 60 | 70 分钟 | 拿满 |
| p3 数颜色 | `reference/p3.py` | 0 / 90 | 65 分钟没写完 | 方案对、时间不够 |
| p4 最长公共子串 | `reference/p4.py` | 0 / 100 | **主动放弃** | 算过的放弃 |
| **合计** | | **170 / 360** | 145 + 65 | |

**p4 的正确解法也写好了**（`reference/p4.py`，二分答案 + 双模数哈希，
$O((|S|+|T|)\log\min(|S|,|T|))$），但**在 240 分钟的模拟里它应该被放弃**——
两道答案放在一起看，正好看清「会做」和「该做」的区别。

参考解一律用纯 Python（这一课的运行环境里没有 numpy），逐组数据的实测耗时：
p1 最大组 0.22 秒、p2 最大组 1.7 秒、p3 最大组 0.67 秒、p4 最大组 1.5 秒、
p5 最大组 0.27 秒。

## 二、目录里有什么

```text
solutions/0031-lab-04-spaced-repetition-drill/
├── README.md               ← 你正在看的这一份
├── timeline.md             ← 填好的限时解题记录（教学重点：怎么记、怎么复盘）
├── explain.md              ← 填好的讲解稿（教学重点：第四段怎么写数字）
├── timeline_template.md    ← 与留白版同一份模板
├── explain_template.md     ← 与留白版同一份模板
├── reference/              ← 五道题的参考解（留白版里**没有**这个目录）
│   └── p1.py … p5.py
├── answers/                ← 判分用的答案位（这里放的是参考解的副本）
├── problems/               ← 与留白版逐字节相同的题面与测试数据
├── score.py                ← 与留白版逐字节相同的判分脚本
├── check_timeline.py       ← 与留白版逐字节相同的流程自检
├── test_data.py            ← 与留白版逐字节相同的数据生成器
└── run_tests.py            ← 与留白版逐字节相同的判分器自检
```

## 三、怎么跑

```text
py score.py            # 应该 360 / 360、退出码 0
py check_timeline.py   # 应该 24 条 PASS、0 条 FAIL、退出码 0
py run_tests.py        # 应该全 PASS、退出码 0
```

## 四、五道题各自的看点

- **p1 舞台高度（二分答案，第 22 课）**：单调性是全部。
  写二分时 `mid` 要取上中位数，否则卡在 `lo = mid` 上死循环。
- **p2 四边形合并（区间 DP，第 26 课）**：比普通石子合并多一维
  「这一段还剩几堆」。这一维是这道题唯一的难点，也是唯一容易错的地方。
- **p3 数颜色（离线 + 树状数组）**：不变式是「扫到 $r$ 时，
  每种颜色只在它最后一次出现的位置上留一个 1」。
  想通了就只剩写代码——而写代码正是这一场里最花时间的部分。
- **p4 最长公共子串（二分 + 哈希，本场超难题）**：
  二维 DP 要 $10^{10}$ 个状态，从读题起就该排除。
  正解思路不长，但实现链上有三处独立的坑。
- **p5 雨天迷宫（0-1 BFS，第 21 课）**：边权只有 0 与 1，
  代价 0 从队头进、代价 1 从队尾进。**性价比最高的一道，应该先做。**

## 五、这一场真正要教的东西

1. **先算总账**：五道题估值合计 470 分钟 > 240 分钟，
   所以「做哪几道」比「怎么做」更早决定胜负。
2. **性价比优先**：p5 是 1.07 分/分钟，p4 是 0.56 分/分钟——差了近 2 倍。
3. **放弃要算过**：写清「预计耗时 > 剩余预算」的具体数字，
   而不是「这道题看起来很难」。
4. **顺序定了就别改**：改了就看不出自己的判断准不准。
5. **留 30 分钟自检**：课件里那 2000 场模拟说这是 17～33 分。