lessons/课程

8.16–8.30 主题课程索引

“8.16–8.30”仅表示本批主题的收集日期，不是学习日程。课程按知识依赖组织，可以随时开始、暂停和回看。

使用入口

• 先读：课程使用说明。
• 每篇讲义都有“尝试路线”和“直接学习路线”。没有时间独立做例题时，也应完成约束翻译、错误路线辨析、关键观察与代码走读。
• 正式例题以 VJudge 为统一入口，同时保留原题来源。题面事实来自 problems/ 中保存的 MHTML；正文只作自包含中文转述。
• 正文只保留类 Python 核心伪代码；完整 C++ 放在仓库根目录 参考实现/ 作为独立附件，并由统一脚本逐文件编译。
• 完成 只表示结构、来源、代码编译、可执行样例/对拍和链接均已检查；其余状态不能视为成品。

建议顺序与状态

顺序	主题与子主题	真正前置	状态
01	欧拉路：判定、Hierholzer、字符串拼接、边定向	DFS、度数、连通性	完成
02	强连通与双连通：SCC、缩点、桥、割点、边双/点双	DFS、栈、树边与返祖边	完成（共 3 节）
03	Bitset：字级并行、集合运算、可达性与复合数据结构	位运算、复杂度估算	完成
04	KMP 与 Manacher：失配、border/周期、回文半径与计数	字符串下标、前缀思想	完成（共 2 节）
05	最短路与类最短路：模型选择、状态扩展、最短路树、次短路、差分约束	基础图论、堆、松弛	完成（共 3 节）
06	最小/大生成树：边分类、替换边、Kruskal 重构树、XOR MST	并查集、树上倍增	完成（共 3 节）
07	二分图：染色、匹配、Kőnig 定理、KM/Hungarian	BFS/DFS、增广思想	完成（共 3 节）
08	高级 Segment Tree / Fenwick Tree：离线计数、动态开点、合并/分裂、可持久化、Beats	已掌握基础树状数组与 Lazy Segment Tree	完成（共 5 节）
09	基环树：找环、剥叶、挂树汇总、函数图计数	树形 DP、拓扑剥叶	完成
10	高斯消元与 CRT：有限域/XOR、秩与解空间、exCRT	模运算、扩展欧几里得	完成（共 2 节）
11	平衡树：FHQ Treap 名次与序列、Splay 区间维护	BST、随机化、Lazy 标记	完成（共 3 节）
12	2016–2026 历年真题：图论、字符串/代数、数据结构、综合建模	前 11 个主题中对应章节	完成（共 10 节、19 道真题）

历年真题学习路线

真题不只按年份排列：前五节保留 CSP/NOIP 年份梯度，后五节按转化工具进入省选综合建模。

1. 2016–2018：期望状态、近最短路计数与基环搜索：P1850、P3953、P5022。
2. 2019–2021：唯一坏对象容斥、函数 DAG 与无歧义区间 DP：P5664、P7077、P7914。
3. CSP-S 2022：可达候选压缩与符号博弈：P8817、P8818。
4. CSP-S 2023：消除栈状态与截止期调度：P9753、P9755。
5. CSP-S 2024：物理条件区间化与双序列状态压缩：P11232、P11233。
6. 省选 2023：区间可达闭包与有限博弈逆推：P9166、P9169。
7. 省选 2024：周期位移与四个线性约束：P10217。
8. 省选 2022–2023：树上边界状态与圆方树划分：P8294、P9167。
9. 省选 2025：推箱子与单调位移压缩：P11833。
10. 省选 2026：星图与 GF(2) 可达空间：P15653，含最小本地协议验证。

下一阶段入口

《CF 2400–2700 高阶扩展路线》 已固定 11 个算法大主题的候选矩阵与深度口径；它属于下一阶段，本轮没有把候选题冒充为已完成讲义。

完成判据

每篇文档必须同时满足以下项目才会在上表标记为“完成”：

1. 目标、自测、动机、步步引导、核心推导、实现、扩展、例题、总结、训练建议齐全。
2. 每道正式例题的题号、标题、来源、限制与特殊条件已由本地题面或原题核验。
3. Hint 分层，完整 Editorial、正确性证明、复杂度和 GNU C++17 参考实现齐全。
4. 所有代码以 g++ -std=c++17 -Wall -Wextra 独立编译；能运行的样例已运行，适合暴力检查的核心算法已对拍。
5. 交互题配最小本地模拟器；不能在线验证的部分明确写成“仅本地协议验证”，不声称通过原评测。