lessons/课程

8.16–8.30 主题课程索引

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

使用入口

• 先读：课程使用说明。
• 每篇讲义都有“尝试路线”和“直接学习路线”。没有时间独立做例题时，也应完成约束翻译、错误路线辨析、关键观察与代码走读。
• 正式例题以 VJudge 为统一入口，同时保留原题来源。题面事实来自 problems/ 中保存的 MHTML；正文只作自包含中文转述。
• 正文只保留类 Python 核心伪代码；完整 C++ 放在仓库根目录 参考实现/ 作为独立附件，并由统一脚本逐文件编译。
• 每个算法主题的 00-课前零食 是正式课前约一周的必修预热：不用 OJ 题，改用“对象—状态—动作—账本”的纸上搭架、小例逐轮模拟、SVG 图示和无需第三方库的 Python 小互动程序。先预测、再展开、最后运行程序；运行方式见互动程序说明。跨度特别大的圆方树、Kruskal 重构树、Splay、文艺平衡树和 ODT 另设专项零食，按下表插入相应正式课之前。
• 完成 只表示结构、来源、代码编译、可执行样例/对拍和链接均已检查；其余状态不能视为成品。

建议顺序与状态

顺序	主题与子主题	真正前置	状态
01	欧拉路径零食 → 欧拉路：判定、Hierholzer、字符串拼接、边定向、掩码图欧拉回路	DFS、度数、连通性	完成（共 3 节，含零食）
02	强/双连通零食 → SCC/桥/割点基础 → 圆方树零食 → 点双/圆方树入口：SCC、缩点、桥、割点、边双/点双	DFS、栈、树边与返祖边	完成（共 5 节，含零食）
03	Bitset 零食 → Bitset：字级并行、集合运算、可达性、补集子掩码隐式图	位运算、复杂度估算	完成（共 3 节，含零食）
04	KMP/Manacher 零食 → KMP 与 Manacher：失配、border/周期、回文半径与计数	字符串下标、前缀思想	完成（共 3 节，含零食）
05	最短路零食 → 最短路与类最短路：模型选择、状态扩展、周期内进度、差分约束	基础图论、堆、松弛	完成（共 5 节，含零食）
06	生成树零食 → 最小/大生成树 → Kruskal 重构树零食 → 重构树与 XOR-MST：边分类、替换边、关联图最大森林、同步缩点	并查集、树上倍增	完成（共 6 节，含零食）
07	二分图零食 → 二分图：染色、匹配、Kőnig 定理、关联图欧拉平衡	BFS/DFS、增广思想	完成（共 5 节，含零食）
08	Segment/Fenwick 零食 → 高级 Segment Tree / Fenwick Tree：离线计数、动态开点、合并/分裂、可持久化、Beats	已掌握基础树状数组与 Lazy Segment Tree	完成（共 6 节，含零食）
09	基环树零食 → 基环树：找环、剥叶、删环边直径、函数图代数构造	树形 DP、拓扑剥叶	完成（共 3 节，含零食）
10	高斯/CRT 零食 → 高斯消元与 CRT：有限域/XOR、零空间覆盖、环空间、非互质周期压缩	模运算、扩展欧几里得	完成（共 4 节，含零食）
11	FHQ 零食 → 按值 FHQ Treap → Splay 基本操作零食 → 文艺平衡树零食 → 隐式 FHQ Treap → Splay 区间暴露 → ODT 零食 → ODT 扩展：FHQ Treap、Splay、随机输入契约与 ODT	BST、随机化、Lazy 标记	完成（共 8 节，含零食）
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，含最小本地协议验证。

高阶扩展入口与状态

《Codeforces 2400–2700 与精选 AtCoder 高阶扩展路线》 记录正式题、衔接题、灵活性实验室与二次筛选池。正式矩阵只保留已形成“来源核验—分级 Hint—Observations—Editorial/证明—伪代码—C++17 附件—样例或对拍”闭环的题；不按题量把候选冒充成完成内容。

主题	本轮正式高阶入口	状态
欧拉路径	掩码图欧拉回路，以及主讲义中的 agc018_f、agc032_c	完成
强/双连通	点双连通与圆方树入口 中 agc071_c	完成
Bitset	补集子掩码隐式图	完成
KMP/Manacher	Manacher 中 qupc2018_h	完成
最短路	周期内进度状态，以及差分约束讲义中的 agc056_c	完成；agc062_d 为灵活性实验室
生成树	关联图最大森林，以及 agc014_e	完成；agc064_b 为衔接题
二分图	关联图欧拉平衡，以及染色讲义中的 agc025_d	完成
Segment/Fenwick	Fenwick 离线计数 中 agc023_e	完成
基环树/函数图	删环边直径与代数构造	完成；agc062_f 为研究导读
高斯/CRT	XOR 路径环空间，以及 abc366_g、agc050_e	完成
平衡树/序列结构	随机输入契约与 ODT	完成

完成判据

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

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