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

  • 常用模板
  • 二维凸包

github地址 https://github.com/caaatch22/algorithm-template