# 限时解题记录（第 31 课 · 实验四）

> 这是**填给自己看**的记录，不是作文。一边做一边填，不要等结束再凭记忆补。
> 这一份是**填好的示例**：它对应 `answer/` 里那五份参考解，
> 以及实测跑出来的那套分（170 / 360）。

## 本场参数（先看一眼，别改）

- 总时长：**240 分钟**
- 题目：**5 道**
- 测试时长与得分：`py score.py` 会跑出每题得分与总分（满分 360）

## 一、通读与估时（15 分钟，不写代码）

先把五道题都读一遍，把下面这张表填满，**再**决定顺序。

| 题 | 读到的数据范围 | 复杂度上限 | 想用的算法族 | 估时（分钟） | 分值 | 性价比 |
| --- | --- | --- | --- | --- | --- | --- |
| p1 舞台高度 | n ≤ 2×10^5、a_i ≤ 10^9 | O(n log n) 到 O(n log V) | 二分答案 | 35 | 30 | 0.86 |
| p2 四边形合并 | n ≤ 300 | O(n^3) 可（300^3/6 = 450 万） | 区间 DP | 70 | 60 | 0.86 |
| p3 数颜色 | n、q ≤ 2×10^5 | 只容得下 O((n+q) log n) | 离线 + 树状数组 | 110 | 90 | 0.82 |
| p4 最长公共子串 | \|S\|、\|T\| ≤ 10^5 | 平方级（10^10）直接出局 | 二分 + 字符串哈希 | 180 | 100 | 0.56 |
| p5 雨天迷宫 | 600×600 = 36 万格 | O(nm) | 0-1 BFS | 75 | 80 | 1.07 |

- **估时**：估 40 分钟的题按 60 分钟算（你的估计一定不准，要留余量）。
- **性价比**：分值 ÷ 估时，越大越先做。

## 二、定顺序（定了就不再改）

- 我定的顺序：**p1 → p5 → p2 → p3 → p4**
- 依据：
  1. **先算总账**：五道题全做要 35 + 70 + 110 + 180 + 75 = **470 分钟**，
     而这场只有 240 分钟。**至少有一道题不可能做完**，所以顺序不是排序问题，是取舍问题。
  2. **按性价比排**：p5（1.07）> p1 与 p2（0.86）> p3（0.82）> p4（0.56）。
  3. **p1 先做**不只是因为性价比：它是最短的一道，先把「一定拿到的那 30 分」装进口袋，
     情绪上也稳。p5 紧接着做，是因为它的模板（0-1 BFS）我刚在第 21 课练过，
     写进肌肉记忆里，出错概率最低。
  4. **p3 放倒数第二**：思路我抓得住（离线 + 树状数组），但它要写两段代码
     （树状数组 + 按右端点分桶），110 分钟的估值里有一大半是写和调。
     放在前面会挤掉稳的那几道，放在最后又可能来不及——所以压在第三道之后。
  5. **p4 放最后、并且是「准备放弃」的那一道**：它的正确解法（二分 + 字符串哈希）
     要从零写一条链，估值 180 分钟。**这只是估时，不是上限**：
     哈希冲突、端点、二分边界这三处任何一处出问题，返工都要 30 分钟起。
     与其赌它，不如按性价比把它排到最后，时间到就跳。
- 我决定**放弃**的是：**p4 · 最长公共子串**
- 放弃的依据（要写时间预算，要有数字）：做完前三道时是第 **185 分钟**，
  剩余预算 **55 分钟**；而 p4 的估值是 **180 分钟**（并且这个估值本身就偏乐观），
  55 < 180 ——**预计耗时是剩余预算的 3 倍以上**，做不完的概率远大于做出来的概率。
  同一段剩余预算投给 p3（估值 110 分钟）至少能拿到部分分。所以按第 31 课的
  「单题耗时 > 总时长就先啃它平均少拿 156.4 分」这条，p4 只在最后有空时才碰。
- 留给自检的时间：**30 分钟**（第 185 到 215 分钟）

> 纪律：顺序定了之后不许重排。重排了就看不出你的判断准不准。

## 三、逐题记录

五道题各一格。**没做出来的也要填全六行**。

### p1 · 舞台高度

- 读题用时：8 分钟
- 定下的算法（为什么，要说数据范围）：**二分答案**。n ≤ 2×10^5、a_i ≤ 10^9，
  逐个数一遍是 O(n) 能接受的，但 h 的取值有 10^9 个，不能枚举 h。
  好在 `sum(a_i // h)` 随 h **单调不增**，满足条件的 h 是一段前缀，所以二分：
  每层 O(n)，共约 30 层 → O(n log V)。
- 写完时刻（第几分钟）：**40 分钟**（读题 12 分钟 + 这道 28 分钟）
- 自检做了什么：跑了题面两个样例；手算核对了样例 2（h=1 时 196 ≥ 100，所以答案是 1）；
  补测 n = 1、k = 1 的边界与「所有 a_i 相同」的一组。
  二分写成 `lo < hi` 配 `mid = (lo + hi + 1) // 2`，特意确认过不会死循环。
- 得分：**30 / 30**
- 丢分丢在哪：没丢分。

### p5 · 雨天迷宫

- 读题用时：7 分钟
- 定下的算法（为什么，要说数据范围）：**0-1 BFS**。n、m ≤ 1000，格子数最多
  100 万，O(nm) 装得下。关键在于边权只有 0 与 1 两种（裂冰连片那一步是 0），
  普通 BFS 只在「每步代价一样」时才对，所以要把队列换成双端队列：
  代价 0 从队头进、代价 1 从队尾进，队列里的距离就始终单调不减，出队即最优。
- 写完时刻（第几分钟）：**75 分钟**（这道 35 分钟，比估的 75 分钟快了 40 分钟）
- 自检做了什么：跑了题面四个样例；补了 n = m = 1（起点即终点）、
  不可达那一档（确认我写的是跑完整队后检查终点的距离是 -1，而不是随手 `return -1`）。
- 得分：**80 / 80**
- 丢分丢在哪：没丢分。

### p2 · 四边形合并

- 读题用时：10 分钟
- 定下的算法（为什么，要说数据范围）：**区间 DP + 剩余堆数这一维**。n ≤ 300，
  所以 O(n^3) 是容得下的（300^3/6 是 450 万级别）。比普通石子合并多一维
  `dp[i][j][l]`（把 a[i..j] 合到剩 l 堆的最小代价）：因为一次合三堆、堆数减 2，
  写到中间会出现「还剩 3 堆」这种形态——不留这一维，就不知道该不该把这次合并的
  代价记上。合并的代价就是这一段的和，所以预先求前缀和。
- 写完时刻（第几分钟）：**145 分钟**（这道 70 分钟，和估计一样）
- 自检做了什么：跑了三个样例；补了 n = 1（代价 0）、n 为偶数（-1）两组边界；
  再拿 41 个数的随机数据与 299 个数的最大数据各跑一遍，确认答案超过 32 位
  却没出问题（Python 整数不用担心）。
- 得分：**60 / 60**
- 丢分丢在哪：没丢分。

### p3 · 数颜色

- 读题用时：8 分钟
- 定下的算法（为什么，要说数据范围）：**离线按右端点排序 + 树状数组**。n、q 都到 2×10^5，
  「每个询问现场数一遍」是 4×10^10 次操作，绝对不行，只容得下 O((n+q) log n)
  （约 720 万次）。关键观察是：颜色 c 在 [l, r] 里出现过，当且仅当 c 在 [1, r] 里
  **最后一次出现的位置 ≥ l**。于是扫到位置 i 时，只在「每种颜色最后一次出现的位置」上
  留一个 1，询问 [l, r] 的答案就是树状数组上 [l, r] 的区间和。
- 写完时刻（第几分钟）：**到 210 分钟还没写完**（估 110 分钟，严重低估）
- 自检做了什么：**只跑了样例**。写完树状数组那一半之后时间就快没了，
  来不及用随机的「现场数颜色」暴力版对拍——这正是第 30 课强调的那一步，
  没做就是没验证过。
- 得分：**0 / 90**
- 丢分丢在哪：方案是对的，但**没写完**。最后 30 分钟本该自检，我把其中 25 分钟
  拿去补 p3，结果两件事都没做完。

### p4 · 最长公共子串

- 读题用时：6 分钟
- 定下的算法（为什么，要说数据范围）：**放弃，不写**。|S|、|T| ≤ 10^5，
  「最长公共子序列」那套二维 DP 的状态数是 10^5 × 10^5 = 10^10 个，
  光开表就放不下（就算一个状态 4 字节也要 40 GB），从读题起就知道这条路不通。
  剩下的解法（后缀结构 / 二分 + 哈希）要写一条完整且容易出错的链，
  估值 180 分钟；而那时剩余预算 55 分钟，55 < 180。
- 写完时刻（第几分钟）：**没写**
- 自检做了什么：没有
- 得分：**0 / 100**
- 丢分丢在哪：主动放弃。这是**算过的放弃**，不是做不出来才放弃：
  放弃的时刻是第 185 分钟，依据是「p4 预计 180 分钟 > 剩余 55 分钟」，
  而不是「这道题看起来很难」。

## 四、复盘（这一场模拟真正的产出）

- 总得分：**170 / 360**（p1 30 + p5 80 + p2 60 + p3 0 + p4 0）
- 估时准不准：**系统性偏乐观，而且偏差分布不均。**
  p1 估 35、实际 28（准）；p2 估 70、实际 70（准）；
  p5 估 75、实际 35（**高估了 40 分钟**）；
  p3 估 110、实际到 210 分钟还没写完（**低估了一倍**）；
  p4 估 180，属于「根本不该排进去」的量级。
  结论：我对手感熟的模板题（p5 这类）估得**太保守**，
  对需要从零搭两段结构、还要调试的题（p3 这类）估得**太乐观**。
  下次给 p3 这种题乘 1.8：110 × 1.8 ≈ 200 分钟——那就意味着它只能排在
  「做完全部的稳题之后、且还有两小时以上」的时候才值得碰。
- 选题顺序的判断：按性价比重排应该是 **p5 → p1 → p2 → p3 → p4**，
  我定的是 p1 → p5 → p2 → p3 → p4，前两道只差 p1 与 p5 的先后——
  这个差别没有代价（两道都做完了）。
  真正的损失在 **p3 被排在 p2 之后**：如果 p5（只用了 35 分钟）之后再压一次
  顺序、把 p3 提前到 p2 前面，p3 能多拿到 70 分钟的预算，就有机会写完；
  p2 那时还剩 140 分钟以上，做完它仍有富余。
  代价是 90 分（p3）换 60 分（p2）的风险——按性价比，p3 本来就该更靠前。
  **一句话：p5 提前做完省下的 40 分钟没有用来重新分配顺序，这是这场最大的浪费。**
- 放弃果断度：**p4 放弃得对**（依据是时间预算与具体数字，不是情绪）。
  但 **p3 没有在正确的时间点放弃**：第 145 分钟做完 p2 时，p3 的剩余预算
  只有 95 分钟，而它需要 110 分钟以上——那时就该判断「它可能写不完」，
  要么压着写完、要么把它的部分时间让给自检。我拖到第 210 分钟才发现写不完。
- 讲解稿的完成度：五道题的四段都写全了，包括放弃的 p4（第 2 段写成
  「我为什么不写它、以及正确解法要靠什么」）。
  「多大的规模会淘汰它」那一段，五道题都落到了具体数字上
  （10^5 / 450 万 / 720 万 / 340 万 / 36 万格这些）。

> 这一场的结果**不是分数，是一份关于你自己的数据**。
> 把它带到第 33 课的综合实战里去。