墨攸的模板整理
墨攸的模板整理
仅整理了提高组大部分所需要的模板
其中带 * 号的是非必要模板 (当然也不保证,最近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$、斜率优化 * -