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

• 常用模板
• 二维凸包