基础
博弈论
| 笔记 | 预览 | 状态 |
|---|---|---|
| Bash博弈 | Bash博弈 | 博客 |
| Fibonacci博弈 | Fibonacci博弈 | 博客 |
| Nim博弈 | Nim博弈 | 博客 |
| SG函数 | SG函数 | 博客 |
| Wythoff博弈 | Wythoff博弈 | 博客 |
图论
| 笔记 | 预览 | 状态 |
|---|---|---|
| Bellman-Ford | Bellman-Ford | 博客 |
| Dijkstra | Dijkstra | 博客 |
| Floyd | Floyd | 博客 |
| Johnson | Johnson | 博客 |
数据结构
字符串
动态规划
基础
枚举
- 排列枚举
- 子集生成
构造
模拟
分治
- cdq
- 树分治
- 点分治
- 边分治
排序
- 快速排序
- 归并排序（含逆序数）
搜索
- 深度优先搜索
- 广度优先搜索
- 双向搜索 双向bfs
- 记忆化搜索
- 启发式搜索
- 二分查找
- 二分答案
- 三分求极值
- ida*
- dancing links
动态规划
经典
- 背包问题（01/完全/多重）
- LCS（最长公共子序列）
- LIS（最长上升子序列）
- LCIS（最长公共上升子序列）
- 最长(不)上升或下降子序列n
数位dp
区间dp
- 石子合并
- 矩阵链乘
- 最优二叉搜索树
环形dp
判定性dp
树形dp
- 树的最大独立集
- 树的直径
- 树的重心
状压dp
- 旅行商问题（TSP）
- 插头DP
- 棋盘DP
优化技术
- 滚动数组
- 二分优化
- 矩阵优化
- 斜率优化
- 四边形不等式优化
- 数据结构优化
- 单调队列优化
- 决策单调性
随机
- 素数测试
- 随机哈希
- 模拟退火
数学
数论
- 素数
- 素数筛
- 埃拉托斯特尼筛法
- 素数测试
- 反素数
- 同余理论
- 欧几里得定理
- 扩展欧几里得
- 中国剩余定理
- 原根/离散对数
- 欧拉函数
- 欧拉降幂公式
- 积性函数
- 高斯消元
- 进制位
组合数学
排列
- 不可重排列
- 可重排列
- 圆排列
- 不尽相异元素全排列
- 多重集的排列
组合
- 不可重组合
- 可重组合
- 不相邻组合
- 多重集的组合
- 大组合数取模
常用公式与定理
- 二项式定理
- 常见恒等式
- 鸽巢原理
- 容斥原理
- 帕斯卡恒等式
- 卢卡斯定理
- 错排问题
- 抽屉原理
常见数列
- 斐波那契数列
- 卡特兰数
- 斯特林数
- 伯努利数
- 欧拉数
递推方程
- 线性递推方程
- 非线性递推方程
- BM算法
母函数
- 普通母函数
- 指数型母函数
置换群Polya计数
快速傅里叶(FFT)
莫比乌斯反演
偏序关系
线性代数
- 矩阵求秩
- 矩阵乘法
- 矩阵快速幂
- 高斯消元
- 行列式计算
- 线性基
计算几何
基本操作
- 误差处理
二维几何
点与向量
- 点与向量的表示
- 内积与外积
- 四则运算
- 对踵点
点与线
- 直线与线段的表示
- 判断点与直线的关系
- 点在直线上
- 两直线交点
- 点到直线的距离
- 点到线段的距离
- 点在直线上的投影点
- 点在线段上
- 两线段相交
多边形
- 三角形
- 三角形面积
- 三角形四心
- 普通多边形
- 多边形表示
- 凸多边形
- Pick定理
圆形
- 圆与直线交点
- 两点交点
- 点到圆切线
- 两圆公切线
- 两圆相交面积
- 点集最小圆覆盖
三维几何
球面几何
凸包
- 凸包算法
- Javis March算法
- Graham Scan算法
- Andrew算法
- Melkman算法
- 三维凸包
离散化
扫描线
旋转卡壳
半平面交
圆并/圆交
博弈
- im游戏
- G函数
- 极大极小过程
图论
基础
- 邻接表/矩阵
- DFS/BFS遍历
- 拓扑排序
- 欧拉路径
- 拓扑排序
- 欧拉图与哈密尔顿图
连通性
- 强连通分量（Tarjan/Kosaraju）
- 双连通分量（割点/桥）
- 割点与桥
- 点双连通分量
- 点割点
- 边割点
- 2-SAT
最短路
- Dijkstra算法
- SPFA算法
- Bellman-Ford算法
- Floyd算法
- 第K短路（A*/Dijkstra）
- 差分约束
生成树
- 最小生成树（Prim/Kruskal）
- 次小生成树
- 最小树形图
- 最优比率生成树
网络流
- 最大流（Dinic/ISAP）
- 费用流（SPFA/ZKW）
- 上下界网络流
- 最小割模型
匹配
- 二分图判断
- 二分图匹配（匈牙利/Hopcroft-Karp）
- KM算法
- 一般图匹配（带花树）
- 稳定婚姻问题
数据结构
线性
- 栈/队列
- 堆（优先队列）
- 链表（静态/动态）
- 块状链表
- 单调栈/队列
字符串
匹配
- KMP算法
- 普通KMP算法
- 拓展KMP算法
- AC自动机
- Sunday算法
- BM算法
Trie字典树
- 字典树
- 01字典树
后缀
- 后缀数组（SA）
- 后缀自动机（SAM）
- 后缀树
回文
- Manacher算法
- 回文自动机
文本处理
- 最小表示法
- 字符串哈希
树形
- 二叉树
- 堆
- 哈夫曼树
- 左偏树
- 线段树（动态开点/可持久化）
- 平衡树（Treap/Splay）
- KD树
- 字典树（Trie）
- 主席树
- 支撑树
- 树套树
- 树剖分
特殊
- 树状数组
- 并查集（带权/扩展）
- 莫队算法（普通/带修）
- 跳跃表
- 舞蹈链（DLX）
stl
- 容器
- 方法
- 迭代器
经典问题
- N皇后
- 汉诺塔
- 哈夫曼编码
- 幻方构造
其他
- 大数
- 高精度
- 日期计算
优化调试
- 快读快写
- 对拍