图论建模
核心不是写最短路，而是把题面里的关系翻译成点与边。分层图、拆点、状态图是省一题的常见入口。
- Dijkstra（堆优化）
- Floyd
- Kruskal
- 拓扑排序
- 差分约束
算法专题
按目标分层：该会什么，该放什么
三档内容对应三种目标。用法很直接：先在第一档自查，能默写就跳过；第二档是冲 CSP-S 一等与省一的主战场； 第三档只在明确要打省选、进省队时才有意义——过早投入高阶专题，是很多人卡住的原因。
第一档 · 自查
应当已经会的东西
这些不解释了，只列标准：不看资料、5 分钟内写出能过的版本。 超过 3 项做不到，先回去补，不要往下看第三档。
- 模拟与枚举：能把题面直接翻译成循环与判断
- 排序：
sort+ 自定义比较，结构体与多关键字排序 - 二分：查找与二分答案，能判断答案是否单调
- 前缀和与差分：一维 / 二维
- 递推与递归：能写出状态转移的雏形
- 贪心：排序后贪心、区间调度，会用对拍否证
- 栈与队列：单调栈、单调队列、滑动窗口
- DFS / BFS：连通块、网格最短路、回溯与剪枝
- 并查集：路径压缩、按秩合并
- 堆与优先队列：多路归并、Dijkstra 的标配
- 基础 DP：线性 DP、01 背包及其变形
- 位运算：
lowbit、异或性质、状态压缩表达
第二档 · 主战场
冲 CSP-S 一等 / NOIP 省一
这一档决定你能否从「会基础」跨到「能拿奖」。要求不只是会模板，而是知道每个模型的适用条件与代价。 建议顺序：图论 → 树 → 数据结构 → DP → 优化。
树上问题
树是最常出现的图。要熟练到能直接写出遍历框架，再往上叠 dfs 序与数据结构。
- 倍增 LCA
- dfs 序 / 欧拉序
- 树形 DP
- 换根 DP
区间与序列结构
看到「单点修改 + 区间查询」先想树状数组，看到「区间修改 + 区间查询」才上懒标记线段树。
- 树状数组
- 线段树 + 懒标记
- ST 表
- 带权并查集
DP 经典模型
难点永远是「状态怎么定义」。定义对了，转移往往是机械的；定义错了，怎么优化都没用。
- 区间 DP
- 状压 DP
- 数位 DP
- 背包变形
- 概率期望入门
DP 优化
能写出 O(n²) 方程只是及格线，能压到 O(n) 才拿得到分。先判断转移式里有没有单调性。
- 滚动数组
- 单调队列
- 决策单调性 / 分治
- 线段树优化
字符串
哈希几乎能解决所有「区间是否相同」类问题，但必须防冲突：双哈希或随机底数，别用裸 131。
- 双哈希
- KMP
- Trie
- Manacher
数论与组合
竞赛用的数论很窄：快速幂、筛法、逆元、组合数取模，加上容斥。写一次模板，每场都用得到。
- 快速幂
- 线性筛
- exgcd / 逆元
- 组合数取模
- 容斥
构造与思维题
没有模板可套，只能靠手玩小数据找规律。训练方法：所有样例都在纸上手算一遍，先猜结论再验证。
- 手玩找性质
- 小数据打表猜结论
- 特判构造
暴力与部分分
OI 赛制里这是最被低估的技能。按子任务分档写暴力，常常比死磕正解得分更高。
- 按子任务分档
- 剪枝 / 记忆化
- 对拍
- 卡时与卡常
第三档 · 省选与 NOI
只在要做省队时才投入
这些专题的共同点是：学习成本高、适用范围窄。省选前的正确顺序是先查漏第二档， 再按「出现频率 × 自己的薄弱程度」挑两三个，而不是全学一遍。
网络流
难点在建模：能不能把题目的限制翻译成容量与边。学会判定「什么时候该想到最小割」比背 Dinic 更重要。
- Dinic
- 费用流
- 最小割建模
- 二分图匹配
树链剖分与 LCT
把树上路径问题转成序列问题。树剖是省选常规武器，LCT 是少数题型的杀手锏。
- 重链剖分
- 树剖 + 线段树
- LCT
点分治与启发式合并
处理「路径计数」与「子树信息合并」的标准工具，配合桶与树状数组使用。
- 点分治
- dsu on tree
- 树上桶
离线算法
共同思路是「换一个更便宜的询问顺序」。看到「多组询问 + 可离线」就该条件反射。
- CDQ 分治
- 整体二分
- 莫队
字符串进阶
后缀数组与 AC 自动机在省选出现频率不低，但代码量大，务必练到能默写。
- AC 自动机
- 后缀数组
- SAM
数学进阶
矩阵加速线性递推几乎必考；多项式与生成函数属于「会一次能用很久」的投入。
- 矩阵快速幂
- 生成函数入门
- NTT
计算几何
代码量大、精度坑多，建议最后再投入。写之前先想清楚用整数还是浮点、怎么处理共线。
- 叉积与面积
- 凸包
- 扫描线
特殊题型
交互、提交答案、强制在线——它们的解法往往不难，难在读不懂题与本地调试。
- 交互题
- 提交答案题
- 通信题
实现与常数
同复杂度下被卡常数是最冤的失分。连续内存、位运算代替取模、减少函数调用都是常规操作。
- 快读
- 内存布局
- 位运算优化
速查
看数据范围，反推目标复杂度
评测机每秒约 10⁸ 次简单运算。带哈希、取模、树的随机访问后常数会变大，实际要按 10⁷–10⁸ 打折扣。
| 数据规模 n | 可接受复杂度 | 通常对应什么做法 |
|---|---|---|
≤ 20 | O(2ⁿ·n) | 状压 DP、子集枚举 |
≤ 300 | O(n³) | Floyd、区间 DP、矩阵乘法 |
≤ 5000 | O(n²) | 点对枚举、二维 DP |
≤ 10⁵ | O(n√n) / O(n log²n) | 分块、莫队、树剖 + 线段树 |
≤ 10⁶ | O(n log n) | 排序、二分、树状数组、最短路 |
≥ 10⁷ | O(n) 或更小 | 扫描、前缀和、单调队列、基数排序 |
下一步：把它排进训练路线 → 或 找题源练手 →