算法竞赛模板库 by 灵茶山艾府 💭💡🎈

算法 Algorithm

由于算法知识点繁杂，将自己学习到的算法、做过的题目分类整理好是有必要的。

一个算法模板应当涵盖以下几点：

对该算法的基本介绍（核心思想、复杂度等）
参考链接或书籍章节（讲得比较好的资料）
模板代码（代码注释、使用说明）
模板补充（常见题型中的额外代码、建模技巧等）
相关题目（模板题、经典题、思维转换题等）

算法目录

不了解 Go？快速入门教程

集合论与位运算
数据结构
- 单调栈 monotone_stack.go
- 单调队列 monotone_queue.go
  - 二维单调队列
- 双端队列 deque.go
- 堆（优先队列）heap.go
  - 支持修改、删除指定元素的堆
  - 懒删除堆
  - 对顶维
  - 前缀中位数
  - 滑动窗口前 k 小元素和
- 并查集 union_find.go
  - 点权并查集
  - 边权并查集（种类并查集）
  - 可持久化并查集
  - 回滚并查集 & 动态图连通性
- 稀疏表（ST 表）sparse_table.go
- 树状数组 fenwick_tree.go
  - 差分树状数组（支持区间加、区间求和）
  - 二维差分树状数组
  - 树套树 & 三维偏序
- 线段树 segment_tree.go
  - 线段树二分
  - 延迟标记（懒标记）
  - 动态开点
  - 线段树合并
  - 线段树分裂
  - 持久化（主席树）
- 0-1 线段树 segment_tree01.go
- 左偏树（可并堆）leftist_tree.go
- 笛卡尔树 cartesian_tree.go
- 二叉搜索树公共方法 bst.go
- Treap treap.go
  - 前 k 小元素和
- 伸展树 splay.go
- 动态树 LCT link_cut_tree.go
- 红黑树 red_black_tree.go
- 替罪羊树 scapegoat_tree.go
- k-d 树 kd_tree.go
- 珂朵莉树（ODT）
  - 数组版 odt.go
  - 平衡树版 odt_bst.go
- 根号分治、分块 sqrt_decomposition.go
- 莫队算法 mo.go
  - 普通莫队
  - 带修莫队
  - 回滚莫队
  - 树上莫队
字符串 strings.go
- 字符串哈希
- KMP
  - pi 函数
  - border
  - 最小循环节
  - fail 树（失配树 / border 树）
- 扩展 KMP（Z algorithm）
- 最小表示法
- 最长回文子串
  - Manacher 算法
- 回文自动机（回文树，PAM）pam.go
- 后缀数组（SA）
- 后缀自动机（SAM）sam.go
- 字典树 trie.go
  - 可持久化字典树
- 0-1 字典树 trie01.go
  - 最大异或和
  - 第 k 大异或和
  - 删除元素
  - 可持久化 0-1 字典树
  - 【研究】0-1 字典树上最多有多少个节点
- AC 自动机 acam.go
数学
- 数论 math.go
  - 辗转相除法（最大公因数 GCD）
  - 类欧几里得算法 ∑⌊(ai+b)/m⌋
  - Pollard-Rho 质因数分解算法
  - 埃氏筛（埃拉托斯特尼筛法）
  - 欧拉筛（线性筛）
  - 欧拉函数
  - 原根
  - 扩展 GCD
    - 二元一次不定方程
  - 逆元
    - 线性求逆元
  - 中国剩余定理（CRT）
    - 扩展中国剩余定理
  - 离散对数
  - 大步小步算法（BSGS）
    - 扩展大步小步算法
  - 二次剩余
  - Jacobi 符号
  - N 次剩余
  - 卢卡斯定理
    - 扩展卢卡斯定理
  - 卡特兰数
  - 默慈金数
  - 那罗延数
  - 斯特林数
    - 第一类斯特林数（轮换）
    - 第二类斯特林数（子集）
  - 贝尔数
  - 欧拉数
  - 数论分块（整除分块）
  - 莫比乌斯函数
  - 莫比乌斯反演
    - 互质计数问题
    - GCD 求和问题
  - 杜教筛
- 组合数学 math_comb.go
  - 常见模型
  - 常用恒等式
  - 容斥原理
- 快速傅里叶变换 FFT math_fft.go
- 快速数论变换 NTT math_ntt.go
  - 包含多项式全家桶（求逆、开方等等）
- 快速沃尔什变换 FWT math_fwt.go
- 连分数、佩尔方程 math_continued_fraction.go
- 线性代数 math_matrix.go
  - 矩阵相关运算
  - 高斯消元
  - 行列式
  - 线性基
- 数值分析 math_numerical_analysis.go
  - 自适应辛普森积分
  - 拉格朗日插值
- 计算几何 geometry.go
  - 线与点
  - 线与线
  - 圆与点
    - 最小圆覆盖
      - Welzl 随机增量法
    - 固定半径覆盖最多点
  - 圆与线
  - 圆与圆
  - 圆与矩形
  - 最近点对
  - 多边形与点
    - 判断点在凸多边形内 $O(\log n)$
    - 判断点在任意多边形内
      - 转角法（统计绕数）
  - 凸包
  - 最远点对
    - 旋转卡壳
  - 半平面交
- 博弈论 games.go
  - SG 函数
动态规划 dp.go
- 背包
  - 0-1 背包
  - 完全背包
  - 多重背包
    - 二进制优化
    - 单调队列优化
    - 同余前缀和优化（求方案数）
  - 分组背包
  - 树上背包（依赖背包）
  - 字典序最小方案
- 线性 DP
  - 最大子段和
  - LCS
  - LPS
  - LIS
    - 狄尔沃斯定理
  - LCIS
  - 长度为 m 的 LIS 个数
  - 本质不同子序列个数
- 区间 DP
- 环形 DP
- 博弈 DP
- 概率 DP
- 期望 DP
- 状压 DP
  - 全排列 DP
  - 旅行商问题（TSP）
  - 子集 DP
  - 高维前缀和（SOS DP）
  - 插头 DP
- 数位 DP
  - 记忆化搜索（同时跑上下界）
- 倍增优化 DP
- 斜率优化 DP（CHT）
- WQS 二分优化 DP（凸优化 DP / 带权二分）
- 树形 DP
  - 树的直径个数
  - 在任一直径上的节点个数
  - 树上最大独立集
  - 树上最小顶点覆盖
  - 树上最小支配集
  - 树上最大匹配
  - 换根 DP（二次扫描法）
    - 简单写法
    - 维护最大次大写法
    - 前后缀分解写法（适用性最广）
图论 graph.go
- 链式前向星
- DFS 常用技巧
- BFS 常用技巧
- 欧拉回路和欧拉路径
  - 无向图
  - 有向图
  - 完全图
- 割点
- 割边（桥）
- 双连通分量（BCC）
  - v-BCC
  - e-BCC
- 仙人掌 & 圆方树
- 最短路
  - Dijkstra
  - SPFA（队列优化的 Bellman-Ford）
    - 差分约束系统
  - Floyd-Warshall
  - Johnson
  - 0-1 BFS（双端队列 BFS）
  - 字典序最小最短路
  - 同余最短路
- 最小环
- 最小斯坦纳树
- 最小生成树（MST）
  - Kruskal
  - Prim
- 单度限制最小生成树
- 次小生成树
- 曼哈顿距离最小生成树
- 最小差值生成树
- 最小树形图
  - 朱刘算法
- 二分图判定（染色）
- 二分图找奇环
- 二分图最大匹配
  - 匈牙利算法
- 带权二分图最大完美匹配
  - Kuhn–Munkres 算法
- 拓扑排序
- 强连通分量（SCC）
  - Kosaraju
  - Tarjan
- 2-SAT
- 基环树
- 最大流
  - Dinic
  - ISAP
  - HLPP
- 最小费用最大流
  - SPFA
  - Dijkstra
- 三元环计数
- 四元环计数
- 树上问题 graph_tree.go
  - 直径
  - 重心
  - 点分治
  - 点分树
  - 最近公共祖先（LCA）
    - 倍增
    - ST 表
    - Tarjan
    - 树上差分
    - 虚树
  - 重链剖分（HLD）
  - 长链剖分
  - 树上启发式合并（small to large）
    - 按大小合并
    - 轻重儿子合并
  - 树分块
  - Prufer 序列
其他
- 位运算笔记 bits.go
  - bitset
  - 区间位运算 trick（含 GCD）
- 二分三分 sort.go
  - 二分答案
  - 0-1 分数规划
  - 整体二分
- 搜索 search.go
  - 枚举排列
  - 枚举组合
  - 生成下一个排列
  - 康托展开
  - 逆康托展开
  - 枚举子集
    - Gosper's Hack
  - 折半枚举（Meet in the middle）
    - 超大背包问题
- 随机算法 rand.go
  - 模拟退火
- 基础算法 common.go
  - 算法思路整理
  - 分组循环
  - 滑动窗口
  - 前缀和
  - 同余前缀和
  - 二维前缀和
  - 菱形区域和
  - 斜向前缀和
    - 菱形边界和
  - 等腰直角三角形区域和
    - 金字塔区域和
  - 二阶差分
  - 二维差分
  - 菱形二维差分
  - 离散化
- 杂项 misc.go
快速输入输出模板 io.go
交互题单 interactive.go

分类题单

如何科学刷题？

滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
二分算法（二分答案/最小化最大值/最大化最小值/第K小）
单调栈（基础/矩形面积/贡献法/最小字典序）
网格图（DFS/BFS/综合应用）
位运算（基础/性质/拆位/试填/恒等式/思维）
图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
🔥动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

欢迎关注 B站@灵茶山艾府

如何选择题目 How to Choose Problems

Rating < 2100

这一阶段主要目标是提高对问题的观察能力。做构造题可以针对性地训练这一点。

选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms)，按照过题人数降序做题，比如 [1700,1900] 区间的就是下面这个链接：

https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900

通过大量的构造题训练，提高观察能力，快速找到切题入口。具体见我在知乎上的这篇回答。

Rating >= 2100（个人训练用，仅供参考）

见识更高的山、更广的海。

按人数从高到低，做 2200+ 的题目。建议不设置难度上限！由于按人数排序，难度分不会太高，不设上限可以避免错过高分好题。

Files

README.md

Latest commit

History

README.md

File metadata and controls

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

算法 Algorithm

算法目录

分类题单

如何选择题目 How to Choose Problems

Rating < 2100

Rating >= 2100（个人训练用，仅供参考）

测试及对拍 Testing

学习资料及题目 Resources

AtCoder 版《挑战程序设计竞赛》

待整理

其他 Others

Useful Tools

Rating and Difficulties

Stay Healthy