This is a collection of my templates used for competitive programming.
动态规划
- 背包问题
- 最长公共子序列
- 最长上升子序列
- 四边形不等式优化
计算几何
- 二维计算几何集合
- 凸包
- 旋转卡壳
- 半平面交
- 反演变换
- 扫描线
- 平面最近点对
- 圆的面积并
- 最小圆覆盖
- Delaunay三角剖分
- 三维基础
- 三维凸包
数据结构
- 并查集
- ST表
- 左偏树
- 树状数组
- 线段树
- Splay
- 无旋Treap
- 带修改主席树
- 分块
- 莫队
- 树上莫队
- 主席树
- 可持久化线段树
- 可持久化平衡树
- 可持久化并查集
- 李超线段树
数学
-
多项式
- 快速傅立叶变换
- 快速数论变换
- 拉格朗日插值
-
数论
- 筛法
- 最大公因数 最小公倍数
- 乘法逆元
- 费马小定理 欧拉定理
- 同余
- 中国剩余定理
- 卢卡斯定理
- 原根
- 数论函数
- 杜教筛
- 反演原理
- 二次互反律
- 二次剩余
- N次剩余
- BSGS
- Miller-Rabin素性测试
- Pollard-Rho大数分解
-
线性代数
- 矩阵
- 高斯消元
- 线性基
-
组合数学
- 常见实例
- 生成排列/组合
- 二项式系数
- 卡特兰数
- 康托展开
- 欧拉数
- 斯特林数
-
其他数学
- 快速幂 快速乘
- 自适应辛普森积分
图论
- 树的直径
- 树的重心
- 树的最小支配集
- 树哈希
- 最近公共祖先
- 虚树
- 树上启发式合并
- 树链剖分
- 点分治
- 动态树
- Prüfer序列
- 生成树
- 最小树形图
- 拓扑排序
- 最短路
- 判负环
- 2-SAT
- 差分约束
- 欧拉路
- Tarjan相关
- 斯坦纳树
- 二分图最大匹配
- 二分图最大权匹配
- 一般图最大匹配
- 最大流
- 费用流
- 上下界网络流
字符串
- 字典树
- 字符串哈希
- KMP
- AC自动机
杂项
- __builtin__
- 读入优化
- 高精度
- 归并排序
- 模拟退火
- 逆序对
- 三分法
- CDQ分治 偏序问题
- 杂项