知识大纲

参考了OI-wiki、CCF 大纲、 和 能力全面提升综合题单。

1. 动态规划

• 背包

• 区间 dp

• 树形 dp（换根 dp）

• DAG 上 dp/拓扑排序后 dp

• 状压 dp

• 数位 dp

• 期望与概率 dp

• dp优化方法

• 决策单调性

2. 字符串

1. 简单字符串
   内容：字符串哈希、字典树、KMP

• z函数（扩展kmp）

• manacher

• 子序列自动机

• SA

• SAM/广义 SAM

• PAM

• AC自动机

• 失配树

• Lyndon 分解

3. 数据结构

• 基础数据结构：队列、栈、并查集、单调栈/单调队列、链表、ST表

• 分块（莫队、定期重构）

• 树状数组

• 各种线段树:
  可持久化线段树（主席树）zkw线段树 李超线段树 吉司机线段树(Segement beats)

• ODT

• 平衡树

• cdq分治

• 替罪羊树

• 猫树

• 左偏树

• 笛卡尔树

• 整体二分

• 树套树

• 可持久化并查集

• 划分树

• LCT

• 树分块

• 块状链表

4. 图论

• 各种图论概念

• 图论 dfs(dfs序)

• 拓扑排序

• LCA

• DSU on tree

• 树链剖分

• 最小生成树

• 次小生成树

• 单源最短路

• 单源次短路

• 全源最短路

• 差分约束

• 同余最短路

• 强连通分量

• 双连通分量

• 二分图

• 割点和桥

• 圆方树

• 虚树

• 树分治/动态树分治

• 边分树/点分树

• 树哈希

• 2-SAT

• 网络流

• 最大团问题（随机化/搜索）

5. 数学

• 位运算

• 高精度

• 光速幂

• 矩阵

• 矩阵快速幂

• 概率论

• 高斯消元

• 博弈论

数论：

• 数论分块

• 欧拉函数

• 筛法

• 分解质因数（Pollard Rho）

• 裴蜀定理

• 逆元

• 线性同余方程

• 中国剩余定理

• 威尔逊定理

• 卢卡斯定理

• 同余方程

• 莫比乌斯反演/欧拉反演

• 杜教筛、min-25筛

• 二次剩余

多项式和生成函数：

• FFT

• NTT

• FWT

• 拉格朗日插值

• 生成函数

• 狄利克雷生成函数

组合数学：

• 排列组合

• 容斥

• 斐波那契数列

• 斯特林数

6. 计算几何（略）

7. 杂项

• 双指针

• 分数规划

• 随机化算法：爬山、模拟退火、随机技巧、哈希

• 贪心

• 搜索
  内容：dfs/bfs、 双向搜索、各种剪枝方法、迭代加深搜索、A*/IDA*、danncing links、\(\alpha -\beta\) 剪枝