# 8.16–8.30 主题课程索引

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

## 使用入口

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

## 建议顺序与状态

| 顺序 | 主题与子主题 | 真正前置 | 状态 |
|---|---|---|---|
| 01 | [欧拉路](01-欧拉路径/01-判定构造与建模.md)：判定、Hierholzer、字符串拼接、边定向、掩码图欧拉回路 | DFS、度数、连通性 | 完成（共 2 节） |
| 02 | [强连通与双连通](02-强连通与双连通/01-强连通分量与缩点.md)：SCC、缩点、桥、割点、边双/点双 | DFS、栈、树边与返祖边 | 完成（共 3 节） |
| 03 | [Bitset](03-Bitset/01-字级并行集合模型与动态匹配.md)：字级并行、集合运算、可达性、补集子掩码隐式图 | 位运算、复杂度估算 | 完成（共 2 节） |
| 04 | [KMP 与 Manacher](04-KMP与Manacher/01-KMP失配边界周期与差分建模.md)：失配、border/周期、回文半径与计数 | 字符串下标、前缀思想 | 完成（共 2 节） |
| 05 | [最短路与类最短路](05-最短路与类最短路/01-建图松弛与01状态图.md)：模型选择、状态扩展、周期内进度、差分约束 | 基础图论、堆、松弛 | 完成（共 4 节） |
| 06 | [最小/大生成树](06-最小与最大生成树/01-割性质与隐式完全图建模.md)：边分类、替换边、关联图最大森林、同步缩点 | 并查集、树上倍增 | 完成（共 4 节） |
| 07 | [二分图](07-二分图/01-二分染色与构造选择.md)：染色、匹配、Kőnig 定理、关联图欧拉平衡 | BFS/DFS、增广思想 | 完成（共 4 节） |
| 08 | [高级 Segment Tree / Fenwick Tree](08-高级线段树与树状数组/01-Fenwick离线计数与序关系.md)：离线计数、动态开点、合并/分裂、可持久化、Beats | 已掌握基础树状数组与 Lazy Segment Tree | 完成（共 5 节） |
| 09 | [基环树](09-基环树/01-剥叶找环与环上统计.md)：找环、剥叶、删环边直径、函数图代数构造 | 树形 DP、拓扑剥叶 | 完成（共 2 节） |
| 10 | [高斯消元与 CRT](10-高斯消元与CRT/01-高斯消元秩解空间与XOR系统.md)：有限域/XOR、零空间覆盖、环空间、非互质周期压缩 | 模运算、扩展欧几里得 | 完成（共 3 节） |
| 11 | [平衡树](11-平衡树/01-FHQ-Treap按值分裂与顺序统计.md)：FHQ Treap、Splay、随机输入契约与 ODT | BST、随机化、Lazy 标记 | 完成（共 4 节） |
| 12 | [2016–2026 历年真题](12-历年真题/01-2016至2018期望最短路与基环建模.md)：图论、字符串/代数、数据结构、综合建模 | 前 11 个主题中对应章节 | 完成（共 10 节、19 道真题） |

## 历年真题学习路线

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

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

## 高阶扩展入口与状态

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

| 主题 | 本轮正式高阶入口 | 状态 |
|---|---|---|
| 欧拉路径 | [掩码图欧拉回路](01-欧拉路径/02-高阶扩展-掩码图上的欧拉回路.md)，以及主讲义中的 `agc018_f`、`agc032_c` | 完成 |
| 强/双连通 | [点双连通与圆方树入口](02-强连通与双连通/03-割点点双连通与圆方树入口.md) 中 `agc071_c` | 完成 |
| Bitset | [补集子掩码隐式图](03-Bitset/02-高阶扩展-补集子掩码隐式图.md) | 完成 |
| KMP/Manacher | [Manacher](04-KMP与Manacher/02-Manacher回文半径与区间计数.md) 中 `qupc2018_h` | 完成 |
| 最短路 | [周期内进度状态](05-最短路与类最短路/04-高阶扩展-周期内进度状态.md)，以及差分约束讲义中的 `agc056_c` | 完成；`agc062_d` 为灵活性实验室 |
| 生成树 | [关联图最大森林](06-最小与最大生成树/04-高阶扩展-关联图中的最大森林.md)，以及 `agc014_e` | 完成；`agc064_b` 为衔接题 |
| 二分图 | [关联图欧拉平衡](07-二分图/04-高阶扩展-关联图欧拉平衡.md)，以及染色讲义中的 `agc025_d` | 完成 |
| Segment/Fenwick | [Fenwick 离线计数](08-高级线段树与树状数组/01-Fenwick离线计数与序关系.md) 中 `agc023_e` | 完成 |
| 基环树/函数图 | [删环边直径与代数构造](09-基环树/02-高阶扩展-删环边直径与代数构造.md) | 完成；`agc062_f` 为研究导读 |
| 高斯/CRT | [XOR 路径环空间](10-高斯消元与CRT/03-高阶扩展-XOR路径的环空间.md)，以及 `abc366_g`、`agc050_e` | 完成 |
| 平衡树/序列结构 | [随机输入契约与 ODT](11-平衡树/04-高阶扩展-随机输入契约与ODT.md) | 完成 |

## 完成判据

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

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