后续学习路线
后续不必按“先把所有算法名称学完,再开始做题”的方式推进。每次选一个当前能理解的任务,学会表示、推导和实现,再进入依赖它的下一步。
| 阶段 | 可以继续学习的内容 | 从已有知识接过去的理由 | 一次练习的完成目标 |
|---|---|---|---|
| 巩固基础解题 | 枚举、模拟、前缀和、双指针、二分、基础贪心的综合题 | 继续练习把文字规则变成循环、判断和单调性 | 独立建模,比较至少两种做法,算出复杂度 |
| 扩展查询结构 | 树状数组、线段树与区间修改 | 前缀和能快速查询;频繁修改后,旧前缀和需要重算,从这个问题引出维护局部信息的结构 | 画出一次修改影响的位置和一次查询合并的片段 |
| 扩展树与图 | 树上 DFS、树上 DP、倍增与 LCA,再学习强连通分量、桥与割点 | 已有根、父节点和深度;进一步处理两点关系、子树信息和图中的连通结构 | 先说明节点、边和答案,再画出状态或搜索记录 |
| 扩展 DP | 区间 DP、树形 DP、状压 DP、计数 DP | 从线性顺序走向区间、树和集合,继续使用“去掉一个决策,得到剩余子问题”的推导 | 展开一个具体状态的候选,推导方程、顺序和答案位置 |
| 扩展字符串与数学 | Trie、KMP;质数筛、组合计数、模运算与扩展欧几里得 | 复用字符串比较、前缀信息、整除和递推,处理重复匹配与更大的计数 | 手算核心状态的变化,说明重用的信息来自哪里 |
| 进入综合训练 | 定时比赛、补题;按需要继续学习网络流、匹配等专题 | 题目不再直接告诉你应使用哪个算法,要把多个模型连接起来 | 比赛后补出模型、证明和反例,再独立实现一次 |
这些专题可以穿插学习。例如线段树与树上问题可以互相促进,字符串和数学也可以按遇到的题目提前阅读。路线中的箭头表示从已有知识继续推进,不是按书名或题号机械排队。
需要查某个专题的概念、例题和实现时,可以阅读 OI Wiki;需要一组按专题排列的练习时,可以使用 CSES Problem Set。洛谷、HDU、Codeforces 与牛客的题目也可以继续做:刚学一个专题时用分类题巩固,之后用混合题和定时比赛练习自己识别模型。