刷题清单 - 综合练习

这份清单现在服务一个新目标
准备浙江中医药大学 ACM 校队提前入队 —— 题量是"入队凭证"里最容易拿的一张。每周节律、比赛清单、要问学长的四个问题都在 ACM 校队选拔训练计划。下面按专题排列，但刷的时候要混着刷，比赛不会按专题出题。做题卡住时先翻 算法总结（一张表：什么时候该抓哪个算法），再回课件。
2026-10-17 全量更新：按 D:\c++\LiangXi_LuoGu 的实际代码逐题打了勾（有代码 = ✅），并把每题的已知瑕疵写在题卡里。

综合轮次推荐（按顺序刷）

  1. ✅ P5740 最厉害的学生 — 结构体 + 遍历/排序
  2. ✅ P1781 宇宙总统 — string 存大数比较
  3. ✅ P1739 表达式括号匹配 — stack
  4. ✅ P1996 约瑟夫问题 — queue / 循环链表
  5. ✅ P1160 队列安排 — 链表插入/删除（指针版超时，数组版已改）
  6. ✅ P1157 组合的输出 — 选/不选
  7. ✅ P2676 Bookshelf B — 贪心
  8. ✅ P1068 分数线划定 — 结构体排序 + 四舍五入
  9. ✅ P1706 全排列 — 回溯 + used[]
  10. ✅ P1591 阶乘数码 — 高精度扩展
  11. ✅ P1303 A*B Problem — 高精度乘法
  12. ✅ P1090 合并果子 — priority_queue
  13. ✅ P1042 乒乓球 — 字符串处理 + 模拟

链表与高精度

✅ P1996 约瑟夫问题 简单
先用 queue 做，再用循环链表做一遍
✅ P1160 队列安排 中等
链表插入/删除。指针版会超时，用数组模拟（P1160_2.cpp 已改数组版）
✅ P1009 阶乘之和 简单
高精度加法 + 高精度乘低精度，已完成
✅ P1591 阶乘数码 简单
在 P1009 基础上统计某个数字出现次数
✅ P1303 A*B Problem 中等
高精度 × 高精度，逐位相乘后统一进位
P1045 麦森数 挑战
选做：高精度 + 快速幂 + 位数公式（本地无代码）

图与图的遍历（0408 · 已完成）

✅ P5318 查找文献 简单
图的基本存储 + DFS/BFS 遍历，注意邻接表要先按编号排序（已提交；本地与参考解随机对拍通过）（0408 课件）
✅ P1605 迷宫 简单
网格上的 DFS + 回溯（visited 标记与撤销）。踩坑：N 是行 M 是列，边界别写反（已提交；边界已修正，本地验证通过）（0408 课件）
✅ P1443 马的遍历 中等
网格上的 BFS 求最短步数，队列存坐标 + 步数（已提交；与参考解逐格比对通过）（0408 课件）

图的进阶：拓扑排序（0409 · 已完成）

✅ P1113 杂务 简单
拓扑排序入门：f[v] = max(f[v], f[u] + len[v])，答案取所有 f 的最大值（已 AC）（0409 课件）
✅ P1807 最长路 中等
DAG 上求最长路（已提交：long long + -1e18 表示不可达）；负权也 OK，不可达输出 -1（0409 课件）
✅ P4017 最大食物链计数 中等
拓扑 + 计数 DP + 取模 80112002（已提交）；起点入度 0、终点出度 0（0409 课件）
✅ P1347 排序 挑战
选做拿下：边读边拓扑判断，区分"能定序 / 发现矛盾 / 还判断不了"。亮点：每次重跑 Kahn 前备份入度数组（0409 课件）

并查集（0410 · 已完成）

✅ P3367 【模板】并查集 简单
路径压缩 + 按大小合并，直接套模板。n ≤ 2×105、m ≤ 106，务必加快读（已提交；400 组随机 + 边界对拍，0 组不一致）（0410 课件）
✅ P1551 亲戚 简单
就是把 P3367 换个故事壳：m 条亲戚关系、p 次询问，输出 Yes / No（已提交、对拍通过；一处小瑕疵仍在：按大小合并写的是比较根的下标，不影响正确性，只是启发式失效）（0410 课件）
✅ P3958 奶酪 中等
三维"空洞相交"翻译成连通性，用虚拟节点代表底面/顶面。两个坑：坐标平方必须 long long、两边都不开根号（已提交；注意坐标可达 ±109，三项平方和理论上仍会超过 long long —— 本地代码还没上 __int128）（0410 课件）

最短路 I：Dijkstra（0411 · 已完成）

✅ P4779 【模板】单源最短路径（标准版） 中等
堆优化 Dijkstra 的主战场：n ≤ 105、m ≤ 2×105、非负权、数据保证 s 能到所有点。必须用优先队列（已提交；代码里仍缺 ios::sync_with_stdio(false); cin.tie(nullptr); 两行，建议补上）（0411 课件）
✅ P3371 【模板】单源最短路径（弱化版） 简单
同一份代码基本能过。专属坑：不可达的点要输出 231-1 = 2147483647（已提交：矩阵换邻接表、去按值传参、输出补齐不可达点、重边保留都已改；只剩一条 -Wsign-compare 警告）（0411 课件）
P1629 邮递员送信 挑战
选做：往返最短路。去程跑一遍 Dijkstra，回程把所有边反向再跑一遍（反图技巧）

最短路 II：Bellman-Ford / SPFA / Floyd（0412 · 已完成）

✅ P3385 【模板】负环 中等
判「从 1 出发可达的负环」，用的是 SPFA + 「路径边数 ent[v] = ent[u] + 1 ≥ n」。对拍结论：样例 NO/YES 正确，200 组随机（含自环、重边、零权环、正权环）与 Bellman-Ford oracle 零不一致，2000 点负权长链不误报；满规模 239 ms（补上快读后 201 ms）。小瑕疵：P3385.cpp:25 一条 -Wsign-compare，且缺两行快读（0412 课件）
⬜ P4779（用 SPFA 再交一次） 选做
已经用堆优化 AC 过；换个算法再交一遍，亲眼看它会不会被卡 —— 比读十篇「SPFA 已死」都管用（0412 课件）

最小生成树：Kruskal / Prim（0413 · 已完成）

✅ P3366 【模板】最小生成树 中等
Kruskal（手写归并排序 + 并查集，凑够 N−1 条边就停，否则输出 orz）。审阅结论：样例 7 ✓、不连通 orz ✓、n=1 输出 0 ✓、重边自环 ✓；400 组随机小图与参考解 0 不一致；满规模 n=5000 m=2×105 121.8 ms（用 sort 是 94.1 ms，都在时限内）。小瑕疵：P3366.cpp:45 一条 -Wsign-compare，auto 返回值 + 递归在别的编译器上可能报错（0413 课件）

二分：查找与二分答案（0414 · P2678 已 AC，P2249 / P1182 待修）

🟡 P2249 【深基13.例1】查找 简单
n ≤ 106、m ≤ 105，输出「第一次出现的编号」或 -1。已交手写 lower_bound（递归版），n ≥ 2 的 300 组随机数据全对、满规模 349 ms 也对；但 n = 1 且查不到时死递归（三个 if 都假设 r - l ≥ 1，l == r 没有出口）→ 改成 while (l < r) 循环版即可（0414 课件）
🟡 P1182 数列分段 Section II 中等
N ≤ 105、答案 ≤ 109，分成 M 段使「每段和的最大值」最小。二分布局正确、200 组小数据全对；但 check 里的 int x 会溢出（n=30, m=1, 全 99999999 → 输出 2199999978，应为 2999999970）→ 把 x 改成 long long（0414 课件）
✅ P2678 [NOIP2015 提高组] 跳石头 挑战
L ≤ 109、N ≤ 50000、最多搬 M 块，让最短跳跃距离最大。已 AC：300 组随机数据与暴力枚举 0 不一致，满规模 14 ms；check 末尾处理「最后一跳不够」时用的是 cnt++（正确写法）（0414 课件）

前缀和 / 差分 / 单调栈（0415 · 已完成）

✅ P3131 [USACO16JAN] Subsequences Summing to Sevens S 简单
前缀和取模，记「每个余数第一次出现的位置」，first[0] = 0 没忘。审阅：200 组随机与暴力 0 不一致，样例 5 ✓，满规模 97.7 ms。可改进：变量名 op/op1/op2 建议改成 a/pre/first，endl 换 '\n'，三个 include 与 bits/stdc++.h 重复（0415 课件）
✅ P2367 语文成绩 中等
差分 d[x] += z; d[y+1] -= z;，最后一遍前缀和取最小值。审阅：200 组随机与暴力 0 不一致。实测满规模 n = p = 5×106（2000 万个整数）共 2.4 s，其中 sort 只占约 350 ms，大头是 cin 读入（约 1.3 s）；改成 fread 快读 + O(n) 求 min 后降到 0.7 s。若 TLE，先换快读，不用急着删 sort（0415 课件）
✅ P5788 【模板】单调栈 中等
从右往左扫，栈里存下标，while (!st.empty() && a[st.top()] <= a[i]) st.pop();。审阅：200 组随机与暴力 0 不一致，样例 3 3 4 0 0 ✓，满规模 n = 3×106 → 583 ms。输出用 cout 实测比改成 string 缓冲 + fwrite（748 ms）还快，不用改（0415 课件）

哈希表：unordered_map / unordered_set（0416 · 已完成）

✅ P3613 【深基15.例2】寄包柜 中等
把 (i, j) 编码成 long long 当键：i * BASE + j（BASE 必须大于 j 的最大值）。k = 0 是清空，要用 erase。已 AC：300 组随机与二维数组对拍 0 不一致，满规模 319 ms；缺两行快读，加上后 64 ms（0416 课件）
✅ P1102 A-B 数对 中等
N ≤ 2×105，统计 a_i − a_j = C 的对数。已 AC，用的正是「先建全表，再对每个 x 查 x + C」的两遍写法（没有踩「扫一遍查 x−C」那个漏逆序对的坑），ans 用了 long long。300 组对拍 0 不一致；满规模 266 ms → 加快读 60 ms。小隐患：i + m 是两个 int 相加，本题刚好不溢出，写成 1LL * i + m 更稳（0416 课件）
✅ P1918 保龄球 简单
值 → 位置，各位置的瓶子数互不相同。已 AC：unordered_map + reserve(n*2)，300 组对拍 0 不一致；满规模 344 ms → 加快读 101 ms → 再换 '\n' 70 ms。实测发现瓶颈全在读入，endl 换成 '\n' 单改几乎无变化（0416 课件）
✅ P1177 【模板】排序 简单
sort 与手写快排（Hoare 双指针版）都已 AC
✅ P1908 逆序对 中等
归并数逆序对，已 AC。踩过两个坑：tmp 写回要用 a[l+t]、相等元素必须走"取左边"分支
✅ P1923 求第 k 小的数 挑战
分治求第 k 小，已 AC——0407 的挑战题拿下

字符串匹配：KMP（0417 · 课件已出，题未做）

⬜ P3375 【模板】KMP 中等
|s1|, |s2| ≤ 106，全大写字母。先按行输出每次出现的位置（1-based，升序），最后一行输出 |s2| 个 pi 值。三个必查点：① 回退是 j = pi[j-1]（不是 pi[j]）；② 匹配成功后立刻 j = pi[j-1]，否则漏重叠匹配（AAAAA 找 AA 只报 1 处）；③ 位置 i - m + 2。实测最坏数据 KMP 1.6 ms vs 暴力 247 ms（0417 课件）

堆与优先队列

✅ P3378 【模板】堆 中等
priority_queue 小根堆，已 AC
✅ P1090 合并果子 中等
小根堆贪心，每次取最小的两堆（重做一遍，答案用 long long）
✅ P1168 中位数 挑战
对顶堆一次过，已 AC——0406 的挑战题拿下

树与二叉树

✅ P1305 新二叉树 简单
二叉树遍历入门，输出前序遍历
⬜ P4913 二叉树深度 简单
树形 DFS，返回左右子树较大深度 + 1（本地无代码）
⬜ P1030 求先序排列 中等
已知中序 + 后序，还原并输出前序（本地无代码）
⬜ P1827 美国血统 中等
已知中序 + 前序，输出后序（本地无代码）
✅ P5076 普通二叉树 中等
BST 插入、排名、第 k 小、前驱后继（已提交；caxun 已补 return，重复值仍会被丢弃那一处判据还在）
⬜ P2234 营业额统计 中等
用 set 找前驱/后继，练习平衡树思维（本地无代码）

栈与队列

✅ P1739 表达式括号匹配 简单
stack 经典，遇 ( 入栈遇 ) 出栈
✅ P1996 约瑟夫问题 简单
queue 模拟，从队首移到队尾

结构体与自定义排序

✅ P5740 最厉害的学生 简单
结构体存学生，遍历找最大值
✅ P1781 宇宙总统 简单
string 存大数 + 排序
✅ P1068 分数线划定 中等
结构体排序 + 四舍五入 + 同分处理

递归与搜索

✅ P1157 组合的输出 简单
纯组合枚举，选/不选，比 P1036 更简单
✅ P1706 全排列 中等
递归枚举排列，需要 used 标记数组

综合

✅ P2676 Bookshelf B 简单
贪心入门，从大到小选
✅ P1042 乒乓球 中等
字符串处理 + 模拟，代码量稍大

已完成（2026-10-17 按 D:\c++\LiangXi_LuoGu 全量核对，后续逐课补）：0406 堆（P3378 / P1090 / P1168）· 0407 排序（P1177 / P1908 / P1923）· 0408 图遍历（P5318 / P1605 / P1443）· 0409 拓扑（P1113 / P1347 / P1807 / P4017）· 0410 并查集（P3367 / P1551 / P3958）· 0411 最短路（P4779 / P3371）· 0412 负环（P3385）· 0413 最小生成树（P3366）· 0414 二分（P2678）· 0415 前缀和 / 差分 / 单调栈（P3131 / P2367 / P5788）· 0416 哈希表（P3613 / P1102 / P1918）· 以及更早的链表、高精度、排序、模拟（P1009 / P1042 / P1059 / P1068 / P1093 / P1157 / P1160 / P1303 / P1305 / P1591 / P1706 / P1739 / P1781 / P1996 / P2676 / P5734 / P5740）
待修后重交：P2249（n = 1 时死递归）· P1182（check 里 int x 溢出）
未做：P4779 用 SPFA 再交一次（选做）· P1629 / P4913 / P1030 / P1827 / P2234 / P1045（选做，本地无代码）
仍可改进的小瑕疵：P1551 按大小合并比的是根下标 · P3958 三项平方和理论上可溢出 · P4779 缺两行快读 · P3371 一条 -Wsign-compare 警告 · P5076 重复值判据 · P3366 一条 -Wsign-compare · 0411–0416 的六份代码都缺 ios::sync_with_stdio(false); cin.tie(nullptr);（实测加两行后满规模快 4-5 倍）
ACM 线：第 1 场（10/18 广工月赛）8 / 14 题、第 66 名；第 2 场（杭师大联考）10 / 10 满分 —— 记录见 ACM 校队选拔训练计划 §9

学习路线图 · 课程对照表