椰程信奥 · 限时训练单
专题10·STL 容器（一） · 限时训练单（50 分钟 · A/B 双卷）
训练说明
| 项目 | 内容 |
|---|
| 题量 | 3 题：论坛帖子（vector） FORUM ／ 哈夫曼树的带权路径长度 HUFFMAN ／ 公交换乘 BUS |
| 时长 | 50 分钟。闹钟一次设定，不暂停、不查资料、不回看课件。 |
| 分层 | A 卷＝冲满分路线；B 卷＝保部分分路线。由教练按上次成绩分派，学生不自选。 |
| 纪律 | 时间到立即停手并提交。没写完的正解也要先把当前能过的版本交上去。 |
| 集训定位 | 5 天集训第 4 天 · 代码量线（T2/T3 不崩） |
一、时间盒（50 分钟）
| 时段 | 时间 | 做什么 | 做完的标志 |
|---|
| 第 1 段 | 0–5′ | 三题全部读一遍，在题号旁写下「这题像哪种模型」和「我先拿哪一档」 | 三行字写完 |
| 第 2 段 | 5–20′ | 第 1 题：先写能过小数据的暴力版，再改正解 | 样例过了、暴力版留着 |
| 第 3 段 | 20–33′ | 第 2 题：同上，先保第 1、2 档 | 样例过了 |
| 第 4 段 | 33–45′ | 第 3 题：同上，时间不够就停在特殊性质档 | 至少有输出 |
| 第 5 段 | 45–48′ | 对拍：小数据把暴力版与正解版跑同一批随机输入，比对 200 组 | 0 组不一致 |
| 第 6 段 | 48–50′ | 提交前 60 秒自检（见第四节） | 四条全部打勾 |
唯一硬规定：时间盒一到就换下一题，哪怕正解只差一行。
复赛里「四题各拿 60 分」永远胜过「一题 100 分、三题 0 分」。
二、A 卷 · 冲满分路线（每题都要冲 100）
- 论坛帖子（vector）（FORUM）：vector + 迭代器按条件查找与删除 易错：erase 之后迭代器失效，必须用返回值接住；下标别越界
- 哈夫曼树的带权路径长度（HUFFMAN）：小顶堆 priority_queue，每次取两个最小的合并，累加 易错：要写
greater<int> 才是小顶堆；n == 1 时答案是 0 不是 w[0] - 公交换乘（BUS）：deque 按时间维护 45 分钟内未使用的券，每张票从队首找可用券 易错：优惠券只能用一次，用过要标记；45 分钟窗口是 t_i − t_j ≤ 45
- 必做：每题都留一份暴力版，用它造小数据对拍 200 组，0 不一致才算过。
三、B 卷 · 保部分分路线（先把能拿的拿稳）
| 题目 | 先拿档位 | 具体动作 | 封顶时间 |
|---|
| 论坛帖子（vector） | 特判 → 暴力 → 特殊性质 | n == 1 → 直接输出那一条；定长数组开大 + 手动移动元素，n ≤ 10⁴ 稳过；只有新增、没有删除/插入 → 就是顺序输出 | 8′ |
| 哈夫曼树的带权路径长度 | 特判 → 暴力 → 特殊性质 | n == 1 → 0；每次线性扫描找最小两个合并，O(n²)，n ≤ 10³ 稳过；所有权重相同 → 就是满二叉树，WPL 可直接算 | 8′ |
| 公交换乘 | 特判 → 暴力 → 特殊性质 | 没有任何地铁（优惠券）记录 → 答案 = 所有票价之和；每张公交票往前扫所有未用券，n ≤ 10³ 时 O(n²) 稳过；所有票价相同 → 直接配对计数 | 8′ |
B 卷不要求满分，要求"零爆零"：每题都至少有输出、都不 RE、都不编译失败。
先保证这件事，再回头补正解。
四、提交前 60 秒自检（四条，逐条打勾）
| ✓ | 检查项 | 典型翻车 |
|---|
| ☐ | 数据范围：int 会不会溢出，要不要 long long | 样例过了、大数据爆 0 |
| ☐ | 边界情形：n = 0 / 1、空输入、最大值，各手算一遍 | 特判档自己写错 |
| ☐ | 文件名与读写：是否 freopen、多测时数组有没有清空 | 本地对、提交 0 分 |
| ☐ | 本讲最易错：erase 之后迭代器失效；priority_queue 默认是大顶堆 | 整题思路对、一分拿不到 |
五、部分分阶梯速查（贴在显示器上）
| 档位 | 预期分 | 做法 | 耗时 |
|---|
| ① 特判档 | 5–10 | n == 0/1、全为 0、已有序等极端情况直接输出 | 2′ |
| ② 暴力档 | 20–30 | 多重循环 / DFS 全枚举 / 朴素 O(n³)，不优化，保证小数据全对 | 8′ |
| ③ 特殊性质档 | 40–60 | 针对部分测试点的性质单独写一份（规模小、值相同、类型单一） | 10′ |
| ④ 正解档 | 100 | 本讲算法 + 与暴力版对拍验证 | 15′+ |
六、教练批阅栏（当堂填完，不留到课后）
| 题目 | 得分 | 丢在哪一档 | 具体原因（写现象，不写"粗心"） | 下次动作 |
|---|
| 论坛帖子（vector） | | | | |
| 哈夫曼树的带权路径长度 | | | | |
| 公交换乘 | | | | |
批阅规则：丢分原因必须写成可执行的现象（例如"递推下标差了一位"），
禁止出现"粗心""没看清"这类无法产生下一步动作的词。
七、课后加练 · 近年 CSP-J/S 真题
| 洛谷 | 题名 | 年份组别 |
难度 | 与本讲的关系 |
|---|
| P7912 | 小熊的果篮 | CSP-J 2021 | 普及+/提高 | 直接对应：队列 / 链表维护连续块 |
加练规则：只做与本讲对应的那一道，做完照样走四档阶梯
（先特判 → 再暴力 → 再特殊性质 → 最后正解），并且必须写暴力版对拍。
真题的价值在于"考法"，不在于"多刷"。