刷题清单 - 综合练习

这份清单现在服务一个新目标
准备浙江中医药大学 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 的 cnt ≥ n 或 Bellman-Ford 的第 n 轮。三个坑：w ≥ 0 的那一行要加双向边、多测要清空 dis/cnt/inq、只判从 1 可达（0412 课件）
⬜ P4779（用 SPFA 再交一次） 选做
已经用堆优化 AC 过；换个算法再交一遍，亲眼看它会不会被卡 —— 比读十篇「SPFA 已死」都管用（0412 课件）
✅ P1177 【模板】排序 简单
sort 与手写快排（Hoare 双指针版）都已 AC
✅ P1908 逆序对 中等
归并数逆序对，已 AC。踩过两个坑：tmp 写回要用 a[l+t]、相等元素必须走"取左边"分支
✅ P1923 求第 k 小的数 挑战
分治求第 k 小，已 AC——0407 的挑战题拿下

堆与优先队列

✅ 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）· 以及更早的链表、高精度、排序、模拟（P1009 / P1042 / P1059 / P1068 / P1093 / P1157 / P1160 / P1303 / P1305 / P1591 / P1706 / P1739 / P1781 / P1996 / P2676 / P5734 / P5740）
未做：P3385（0412 配题，本地还没有代码）· P1629 / P4913 / P1030 / P1827 / P2234 / P1045（选做，本地无代码）
仍可改进的小瑕疵：P1551 按大小合并比的是根下标 · P3958 三项平方和理论上可溢出 · P4779 缺两行快读 · P3371 一条 -Wsign-compare 警告 · P5076 重复值判据
ACM 提前入队线：题量与节律见 ACM 校队选拔训练计划，下一场 10/18 广工月赛

学习路线图 · 课程对照表