当前最新普通版发布版本为 v1.2.0 ， 最新打印版发布版本为 v1.2.0 (总词数约10.0w(含代码))

成品为 template.pdf (移步 releases 查看/下载)

因打印版 pdf 目录页码制作困难，因此直到版本 v1.3.0 之前不会更新打印版，只会更新普通发布版。另，由于本人退役，未来预计将不会有大更新。

---

模板简介

这是一份适用于算法竞赛的 C++ 为主的代码模板集合。主要用作 ICPC区域赛/CCPC 比赛时的参考资料，可打印。本模板收录大部分铜牌算法和银牌算法，不收录过于基础的内容(如栈)，也不收录过难的内容(如广义后缀自动机)。不定期更新。

本模板主要浓缩提炼自我的算法笔记(三份笔记，折合约28.5万+2.5万+5万=36万字(含代码))，历时约两周爆肝制成，因时间仓促，难免可能产生纰漏，如果您发现了任何错误之处或者如果您对本模板的内容增删改有任何意见或建议，欢迎您随时提出 >_<

目前版本使用 Typora 制作，有生之年有概率考虑使用 LaTeX 重做本模板。碍于本人技术有限，目前目录页码是手动制作的(使用 Adobe Acrobat DC 逐目录项修改)，因此可能会出现页码不正确，若发现欢迎纠正

目前模板收录的模块大致如下：(具体请参见详细目录)

1. 数学

   主要含组合数学、数论、计算几何、博弈论等

2. 数据结构

3. 图论

   主要含树上问题、图论基础、二分图、网络流等

4. 动态规划

5. 字符串

6. 杂项

   主要含排序、二分、搜索、高精度、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/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 内容