icpc模板
/
[pdf]
algorithm-template
Competitive Programming template
basic algorithm
- 双指针
- 离散化，去重
- 前缀和与差分
- 二分
- 单调栈
- 单调队列
- 尺取法
- 归并排序，快速排序，第k小
- 树的中心
- 拓扑排序
math
- 素数，筛素数，素性测试， 反素数
- 质因数分解，预处理质因数
- 欧拉函数
- 组合数
- 拓展欧几里得，线性同余方程
- 中国剩余定理
- 容斥原理
- 高斯消元，高斯异或
- 矩阵乘法
- 博弈论，Nim游戏
- 莫比乌斯反演
- BSGS
- FFT
- 生成函数
- 线性基
date strcture
- 并查集
- Sparse table
- Trie, 01Trie
- 树状数组
- 线段树，扫描线
- 树链剖分
- 可持久化线段树，kth number, 主席树
- splay
- 分块
- 莫队
- 点分治
- kdtree
Graph
- Floyd
- bellman-ford, spfa，判负环
- dijkstra， 拆点
- 分层图最短路
- 差分约束
- 最小生成树 prim, kruskal
- 瓶颈生成树
- kruskal重构树
- lca
- 二分图匹配
- 欧拉回路欧拉路径
- 强连通分量
- 2-sat
- 网络流相关
string
- 字符串hash
- KMP， 前缀函数
- Z-algorithm
- ac自动机
- SA
- SAM
dp
- 01pack, 完全背包，多重背包及优化，分组背包
- 线性dp, LCS, LIS, 编辑距离
- 区间dp 字符串压缩
- 数位dp
- 状压dp
- 树形dp
- 基环树dp
- 单调队列优化dp
- 斜率优化dp
Geometry
- 常用模板
- 二维凸包