当前最新普通版发布版本为 v1.2.2
, 最新打印版发布版本为 v1.2.0
(总词数约10.0w(含代码))
成品为 template.pdf
(移步 releases 查看/下载)
因打印版
v1.3.0
之前不会更新打印版,只会更新普通发布版。另,由于本人退役,未来预计将不会有大更新。
这是一份适用于算法竞赛的 C++ 为主的代码模板集合。主要用作 ICPC区域赛/CCPC 比赛时的参考资料,可打印。本模板收录大部分铜牌算法和银牌算法,不收录过于基础的内容(如栈),也不收录过难的内容(如广义后缀自动机)。不定期更新。
本模板主要浓缩提炼自我的算法笔记(三份笔记,折合约28.5万+2.5万+5万=36万字(含代码)),历时约两周爆肝制成,因时间仓促,难免可能产生纰漏,如果您发现了任何错误之处或者如果您对本模板的内容增删改有任何意见或建议,欢迎您随时提出 >_<
目前版本使用 Typora 制作,有生之年有概率考虑使用 LaTeX 重做本模板。碍于本人技术有限,目前目录页码是手动制作的(使用 Adobe Acrobat DC 逐目录项修改),因此可能会出现页码不正确,若发现欢迎纠正
目前模板收录的模块大致如下:(具体请参见详细目录)
-
数学
主要含组合数学、数论、计算几何、博弈论等
-
数据结构
-
图论
主要含树上问题、图论基础、二分图、网络流等
-
动态规划
-
字符串
-
杂项
主要含排序、二分、搜索、高精度、STL 等
正文源码在 template.md
文件中
推荐编辑/阅读该源码文件所用工具为 Typora beta 0.11.17
部分代码源码在
codes/
内
Star it to keep trace of any possible updates!
lr580's 算法模板
数学
公式
常用符号
组合数学
排列组合
卡特兰数
斯特林数
生成函数
球盒问题
其他
分拆数
贝尔数
欧拉数
复杂度
数列
高等数学
线性代数
概率论
其他
数论
基础性质
素数
素性测试
埃氏筛
欧拉筛
pollard-rho算法
Meissel-Lehmer算法
拓展欧几里得定理
取模公式
欧拉函数
中国剩余定理
BSGS
计算几何
向量
线段
点到直线距离
线段相交判定
直线交点
点在直线投影
多边形
极角排序
凸包
Graham
Andrew
直径
点与凸包相交
两凸包相交
扫描线
杂项
Pick定理
平面最近点对
随机增量法
博弈论
多项式
FFT
NTT
分治 FFT
FWT
拉格朗日插值法
杂项
矩阵加速
高斯消元
康托展开
自适应辛普森法
数据结构
ST表
线段树
常见应用
区间加法
区间加乘
区间查重
区间最值
历史最值
zkw线段树
单点修改
区间修改
猫树
主席树
可持久化数组
静态区间第k小
树状数组
静态区间最值
动态整体第k小
动态区间第k小
二维树状数组
平衡树
FHQ-Treap
AVL
Splay
K-D Tree
堆
可删堆
笛卡尔树
可并堆
珂朵莉树
并查集
种类并查集
加权并查集
可撤销并查集
可持久化并查集
图论
树
重心
直径
最近公共祖先
树上k级祖先
LCA应用
前缀和差分
两点距离
路径相交
其他
树链剖分
启发式合并
虚树
点分治
Prufer 序列
二叉树遍历
先中求后
中后求先
先后求中
杂项
随机游走
最小距离和
基本概念
最短路
floyd
Bellman-Ford
SPFA
Dijkstra
Johnson
差分约束
拓扑排序
最小生成树
kruskal
prim
Borůvka
严格次小生成树
连通性
连通分量
强连通分量
割点
桥
点双连通分量
边双连通分量
圆方树
2-SAT
匹配问题
网络流
最大流
EK 算法
Dinic算法
最小费用最大流
最小割
杂项
欧拉图
哈密顿图
竞赛图
动态规划
模板
背包问题
字符DP
树上DP
区间DP
状压DP
数位DP
杂项
最长公共子序列
编辑距离
约瑟夫问题
字符串
字符串哈希
KMP
manacher
字典树
AC自动机
后缀数组
基础
LCP
SA-IS
后缀自动机
FFT字符串匹配
子序列自动机
最小表示法
Lyndon分解
杂项
排序
计数排序
基数排序
归并求逆序对
二分
最长单调序列
最长公共排列
二分答案
最小中位数子矩阵
最大子串平均值
其他
整体二分
wqs二分
前缀和/差分
搜索
IDA*
双向搜索
折半搜索
随机化
莫队
普通
带修
树上
回滚
高精度
C++
FFT 乘法
java 高精度
python 高精度
悬线法
程序语法
常规运算
位运算
指针
I/O
其他
STL
函数
xx_bound
字符串
正则表达式
随机数
杂项
数据结构
string
vector
set
map
bitset
其他
pb_ds
卡常
快读/写
其他
-
23/10-27 - 24/06/05 (
v1.2.2
)-
添加了动态开点线段树模板
-
微加了位运算语法应用
-
添加了暴力 LCA
-
微修了 Dijkstra 最短路应用例子表述错误、朴素法代码等
-
添加了调试输出版本的语法
-
添加了枚举组合 Gosper's Hack 模板
-
修正了整数三分模板
-
增加了树上 k 级祖先倍增法
-
增加了背包方案数模板
-
修正了 Miller Rabin 素性测试复杂度
-
微加了差分约束内容
-
微修了 STL vector 语法表述错误
-
-
23/10/22 - 23/10/26 (
v1.2.1
)-
重制了匹配问题等目录排版
-
微加了 STL 内容
-
添加了树状数组上倍增、线段树上二分、pb_ds 哈希表
-
修正了整数三分模板
-
添加了立体计算几何公式
-
-
23/10/19 - 23/10/21 (
v1.2.0
)-
添加了快速矩阵前 n 项和模板
-
添加了最小割模板
-
微调了 SG 定理应用
-
重制了部分求导、积分等高数公式表
-
添加了多项式全家桶、斯特林数、按列分拆数模板
-
微加了 STL 内容
-
添加了点在凸包、凸包交判定(闵可夫斯基和)模板
-
添加了最小边覆盖模板
-
微加了最短路应用
-
微加了 LIS 应用
-
添加了子序列自动机
-
添加了 FWT 模板
-
删除了最小成本排序例题
-
微加了归并排序应用
-
添加了枚举子集模板、数位 DP 模板
-
微加了 KMP, manacher 应用
-
添加了 wqs 二分内容
-
添加了悬线法模板
-
重制了编辑距离模板
-
-
22/11/20 - 22/12/3 (
v1.1.2
)-
添加了整数三分代码
-
修改了部分 KMP / 字符串例题描述
-
添加了 prim 暴力模板和最小生成树输出方案代码
-
添加了 floyd 输出方案代码
-
微加了 manacher 内容
-
添加了上下取整及其不等式公式
-
-
22/10/24 - 22/11/11 (
v1.1.1
)- 添加了树上随机游走
- 添加了带权并查集例题
- 添加了负环输出方案模板
- 添加了最短路少量内容
- 修改了 STL priority_queue 的错误描述
- 微调了 tarjan 模板代码
- 添加了高阶前缀和公式
- 添加了错位排列数少量内容
- 添加了 BSGS, exBSGS 和 exGCD 的另一种实现模板
- 添加了中国剩余定理少量内容
- 添加了矩阵快速幂常见建模例子
- 添加了 exLucas 模板
- 修改了同余一条性质的错误表述
- 添加了 STL multiset 部分内容
-
22/10/19 - 22/10/20 (
v1.1.0
)- 添加了哈密顿图结论
- 添加了划分数结论
- 修改了点双连通分量参考代码
- 添加了斐波那契数列等新的数学结论
- 添加了竞赛图兰道定理等结论
-
22/09/01 - 22/10/18 (
v1.0.5
)-
添加了边双连通分量例题
-
添加了可撤销并查集+线段树分治动态判二分图的例题
-
修改了 manacher 一处错误
-
修改了数论基础同余的一处书写错误
-
添加了封装的最小费用最大流模板
-
添加了后缀数组内容
-
添加了 STL 重载 unordered_set 内容
-
添加了 pollard_rho 算法
-
添加了斐波那契数列模数循环节结论
-
添加了线性快速幂
-
添加了差分约束算法
-
-
22/06/10 - 22/08/27 (
v1.0.4
)-
微改了 STL 的 nth_element 和 inplace_merge
-
微改了复杂度一节的排版错误
-
删除了 STL 的 string 重复内容
-
添加了多项式一节,增加 NTT 和分治 FFT 内容
-
修正了线段树区间最值例题表述错误
-
更换了欧拉筛一道例题
-
添加了 tarjan 算法求点双连通分量和圆方树内容
-
-
22/05/17 - 22/05/25 (
v1.0.3
)- 增加了stringstream
- 增加了普通莫队、带修莫队、树上莫队和回滚莫队算法
- 增加了set部分内容
- 增加了2-SAT算法
-
22/04/19 - 22/04/22 (
v1.0.2
)- 增加了KMP算法周期与border
- 删除了凸包一节无关多余内容
- 增加了另一种写法的C语言快读
- 修正了计算几何判断线段相交的错误方法
- 增改了随机化的程序语法、公式和爬山算法及模拟退火例题
- 重制了珂朵莉树参考模板
- 微增了博弈论理论内容
-
22/04/06 - 22/04/07 (
v1.0.1
)- 增加了位运算一节少量内容
- 修改部分点分治笔记
- 增加了 Java 快读快写
- 增加可删堆,并与笛卡尔树、可并堆合并为堆专题
-
22/04/04 (
v1.0.0
)- 稍微补充了少量内容
- 发布了第一版模板
-
22/04/03
- 补充了数论、高等数学、杂项内容
- 增加了博弈论、字符串、计算几何、线性代数和概率论、动态规划内容
-
22/04/02
- 增加了数论主要内容、高等数学内容
-
22/04/01
- 增加了图的连通性、组合数学、数学杂项内容
-
22/03/31
- 增加了拓扑排序、最小生成树、二分图匹配、网络流内容
-
22/03/30
- 增加了zkw线段树、猫树、K-D Tree内容,修改了部分内容
- 增加了图概念、最短路内容
-
22/03/29
- 增加整体二分、LIS、前缀和/差分内容
- 增加了搜索、二分答案内容
-
22/03/28
- 增加加权并查集内容
-
22/03/26
- 补充树内容
- 增加线段树、树状数组、平衡树等数据类型
-
22/03/25
- 补充 STL 内容
- 增加排序、组合数学、快读快写、高精度、树
-
22/03/24
- 开始模板编制工作
- 增加部分数学公式、大部分 STL 内容