墨攸的模板整理
墨攸的模板整理
仅整理了提高组大部分所需要的模板
其中带 * 号的是非必要模板 （当然也不保证，最近CCF真是什么都考）
但是我寻思着什么莫队退火FFT LCT应该也不会考啊，所以就不加了qaq
里面加入了一些自制模板，只是方便与代码对照，所以大部分无数据（以后有时间了可能会补上）。
动态更新（因为退役了，所以大概率不会更新了...）
-
字符串
- ①[【模板】字符串哈希](https://www.luogu.org/problem/P3370) ：——： [【代码】](https://www.luogu.org/paste/k0xrz5sn) - ②【暂无模板】哈希表 ：——： 【暂无代码】 $2$、$KMP$算法 $3$、$Trie$字典树 $4$、$AC$自动机 * -
数据结构
- ①【暂无模板】邻接链表存图 ：——： [【代码】](https://www.luogu.org/paste/2aqm1s92) - ② 待定 $2$、$RMQ$问题与$ST$表 - ①[【模板】ST表](https://www.luogu.org/problem/P3865) ：——： [【代码】](https://www.luogu.org/paste/gcinxqqn) - ②[【拓展】树状数组写法](https://www.luogu.org/problem/P3865) ：——： [【代码】](https://www.luogu.org/paste/h5hexvrj) * $3$、树状数组 - ①[【模板$1$】单点查询区间修改](https://www.luogu.org/problem/P3374) ：——： [【代码】](https://www.luogu.org/paste/mismqb4g) - ②[【模板$2$】区间查询单点修改](https://www.luogu.org/problem/P3368) ：——： [【代码】](https://www.luogu.org/paste/f18inkqd) - ③[【拓展】区间查询区间修改](https://www.luogu.org/problem/P3372) ：——： [【代码】](https://www.luogu.org/paste/r152x1k0) - ④[【类模板】二维区间查询区间修改](https://www.luogu.org/problem/P4514) ：——： [【代码】](https://www.luogu.org/paste/2v4rmiln) * $4$、线段树 - ①[【模板$1$】加法操作的线段树](https://www.luogu.org/problem/P3372) ：——： [【代码】](https://www.luogu.org/paste/ohk8bbdf) - ②[【模板$2$】加乘操作的线段树](https://www.luogu.org/problem/P3373) ：——： [【代码】](https://www.luogu.org/paste/clhr4oqy) $5$、$LCA -
①【模板】最近公共祖先（LCA，倍增写法） ：——： 【代码】
-
②【模板】最近公共祖先（LCA，RMQ优化） ：——： 【暂无代码】 *
-
③【模板】最近公共祖先（LCA，树链剖分写法） ：——： 【暂无代码】 *
$7$、平衡树Treap * $8$、主席树 * -
-
图论
- ①[【模板】并查集](https://www.luogu.org/problem/P3367) ：——： [【代码】](https://www.luogu.org/paste/lmbpobii) - ② 待定 $2$、最小生成树 - ①[【模板】最小生成树（kruskal算法）](https://www.luogu.org/problem/P3366) ：——： [【代码】](https://www.luogu.org/paste/wkve79ja) - ② 待定 $3$、最短路 - ①[【自制模板】多源最短路（floyd算法）](https://www.luogu.org/problem/U92916) ：——： [【代码】](https://www.luogu.org/paste/kexqbfmw) - ②[【模板】单源最短路（SPFA算法，弱化版）](https://www.luogu.org/problem/P3371) ：——： [【代码】](https://www.luogu.org/paste/i8cci73e) - ③[【模板】单源最短路（dijkstra算法，标准版）](https://www.luogu.org/problem/P4779) ：——： [【代码】](https://www.luogu.org/paste/d0v5bil1) - ④[【拓展】单源最短路（双端队列优化SPFA）](https://www.luogu.org/problem/P3371) ：——： [【代码】](https://www.luogu.org/paste/c37ughwi) * $4$、差分约束 - ①[【自制模板】差分约束](https://www.luogu.org/problem/U92805) ：——：[【代码】](https://www.luogu.org/paste/2sgukdmd) - ② 待定 $5$、拓扑排序 - ①[【自制模板】拓扑排序](https://www.luogu.org/problem/U92914) ：——： [【代码】](https://www.luogu.org/paste/chf751to) - ②[【类模板】菜肴制作](https://www.luogu.org/problem/P3243) ：——： [【代码】](https://www.luogu.org/paste/szyih9fr) $6$、强连通分量与缩点 - ①[【类模板】受欢迎的牛](https://www.luogu.org/problem/P2341) ：——： [【代码】](https://www.luogu.org/paste/dsiq0kcx) - ②[【模板】缩点](https://www.luogu.org/problem/P3387) ：——： 【暂无代码】 $7$、割点与桥 - ①[【模板】割点](https://www.luogu.org/problem/P3388) ：——： 【暂无代码】 - ② 待定 $8$、欧拉回路 $9$、负环 $10$、二分图匹配 * -
数论
- ①[【模板】线性筛素数（判断一个数）](https://www.luogu.org/problem/P3383) ：——： [【代码】](https://www.luogu.org/paste/sbvta7n3) - ②【暂无模板】埃式线性筛（计算前$n$个质数）：——：【暂无代码】 $2$、最大公约数（gcd） $3$、快速幂与快速乘 - ①[【模板】快速幂](https://www.luogu.org/problem/P1226) ：——： [【代码】](https://www.luogu.org/paste/ej3lgjd4) - ②[【自制模板】快速乘](https://www.luogu.org/problem/U92919) ：——： [【代码】](https://www.luogu.org/paste/hzso5dhn) $4$、同余基础 $5$、扩展欧几里得（ex_gcd） - ①[【类模板】同余方程](https://www.luogu.org/problem/P1082) ：——： [【代码】](https://www.luogu.org/paste/nm9tn3be) - ② 待定 $6$、乘法逆元 - ①[【模板】线性求逆元](https://www.luogu.org/problem/P3811) ：——： [【代码】](https://www.luogu.org/paste/itucuybf) - ②[【自制模板】单独求逆元（快速幂写法）](https://www.luogu.org/problem/U92920) ：——： [【代码】](https://www.luogu.org/paste/zqptblcn) - ③[【自制模板】单独求逆元（exgcd写法）](https://www.luogu.org/problem/U92920) ：——： [【代码】](https://www.luogu.org/paste/cdm8vtxc) $7$、矩阵加速 - ①[【模板】矩阵快速幂](https://www.luogu.org/problem/P3390) ：——： [【代码】](https://www.luogu.org/paste/rc8cxo1i) - ②[【模板】矩阵加速](https://www.luogu.org/problem/P1939) ：——： [【代码】](https://www.luogu.org/paste/r9ewsgyq) - ③[【类模板】斐波拉契数列](https://www.luogu.org/problem/P1962)：——：[【代码】](https://www.luogu.org/paste/wmwj9qr9) $8$、组合数学基础 $9$、中国剩余定理 * -
动态规划
（由于
dp 题目没有什么固定的模板，所以选了一些典型题目挂在了上面...）$2$、线性$dp -
①【二分/BIT优化线性
dp 】导弹拦截 ：——： 【代码】 -
② 待定
3$、区间$dp 4$、树形$dp -
①【树的最大独立集】战略游戏 ：——： 【代码】
-
②【普通树的
dp 问题】手机网络 ：——： 【代码】 -
③【由根分为左右子树两部分情况】二叉苹果树 ：——： 【代码】
-
④【背包类树形
dp 】选课 ：——： 【代码】
5$、状压$dp -
①【普通状压
dp 】玉米田 ：——： 【代码】 -
② 待定
$7$、单调队列优化 * $8$、斜率优化 * -