OI模板集-提高篇 Part II

[返回目录](https://www.luogu.com.cn/training/428352) # 0x0 前言 这个题单是个人根据 NOI 大纲 2025 版中的内容以及个人经验所总结出的 OI 中较为模板化的题目。 此题单的优点： - 紧随 NOI 大纲； - 选取题目典型、有代表性； - 附 OI Wiki 链接，供新手学习并深入理解算法。 # 0x1 提高组（标准） **这一部分只涉及在 NOI 大纲 - 提高级中出现的知识点。** ## 0x10 数据结构 - 单调队列：[P1886 滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/monotonous-queue/)】 - ST 表：[P3865 【模板】ST 表 && RMQ 问题](https://www.luogu.com.cn/problem/P3865)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/sparse-table/)】 - 并查集：[P3367 【模板】并查集](https://www.luogu.com.cn/problem/P3367)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/dsu/)】 - 二叉堆：[P3378 【模板】堆](https://www.luogu.com.cn/problem/P3378)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/binary-heap/)】 - 树状数组：【OI Wiki 中链接：[this](https://oi-wiki.org/ds/fenwick/)】 - [P3374 【模板】树状数组 1](https://www.luogu.com.cn/problem/P3374) - [P3368 【模板】树状数组 2](https://www.luogu.com.cn/problem/P3368) - 线段树：【OI Wiki 中链接：[this](https://oi-wiki.org/ds/seg/)】 - [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) - [P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373) - 字典树：[P8306 【模板】字典树](https://www.luogu.com.cn/problem/P8306)【OI Wiki 中链接：[this](https://oi-wiki.org/string/trie/)】 - 笛卡尔树：[P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/cartesian-tree/)】 - 平衡树：【OI Wiki 中链接：[this](https://oi-wiki.org/ds/bst/#%E5%B9%B3%E8%A1%A1%E6%A0%91%E7%AE%80%E4%BB%8B)】 - [P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) - [P6136 【模板】普通平衡树（数据加强版）](https://www.luogu.com.cn/problem/P6136) - 哈希表：[P11615 【模板】哈希表](https://www.luogu.com.cn/problem/P11615)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/hash/)】 ## 0x11 算法 ### 0x110 算法策略 & 基础算法 - 离散化：[B3694 数列离散化](https://www.luogu.com.cn/problem/B3694)【OI Wiki 中链接：[this](https://oi-wiki.org/misc/discrete/)】 - 扫描线：[P5490 【模板】扫描线 & 矩形面积并](https://www.luogu.com.cn/problem/P5490)【OI Wiki 中链接：[this](https://oi-wiki.org/geometry/scanning/)】 - 分治：【OI Wiki 中链接：[this](https://oi-wiki.org/basic/divide-and-conquer/#%E5%88%86%E6%B2%BB)】 ### 0x111 字符串 - KMP 算法：[P3375 【模板】KMP](https://www.luogu.com.cn/problem/P3375)【OI Wiki 中链接：[this](https://oi-wiki.org/string/kmp/)】 - 字符串哈希：[P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370)【OI Wiki 中链接：[this](https://oi-wiki.org/string/hash/)】 - Manacher 算法：[P3805 【模板】manacher](https://www.luogu.com.cn/problem/P3805)【OI Wiki 中链接：[this](https://oi-wiki.org/string/manacher/)】 ### 0x112 搜索 - 记忆化搜索：【OI Wiki 中链接：[this](https://oi-wiki.org/dp/memo/)】 - 启发式搜索（A*）：[P2324 [SCOI2005] 骑士精神](https://www.luogu.com.cn/problem/P2324)【OI Wiki 中链接：[this](https://oi-wiki.org/search/heuristic/)】 - 双向搜索：[P4799 [CEOI2015 Day2] 世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799)【OI Wiki 中链接：[this](https://oi-wiki.org/search/bidirectional/)】 - 迭代加深搜索：[P1763 埃及分数](https://www.luogu.com.cn/problem/P1763)【OI Wiki 中链接：[this](https://oi-wiki.org/search/iterative/)】 ### 0x113 图论 - 最小生成树：[P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/mst/#%E5%AE%9A%E4%B9%89)】 - 次小生成树：[P4180 [BJWC2010] 严格次小生成树](https://www.luogu.com.cn/problem/P4180)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/mst/#%E6%AC%A1%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91)】 - 单源最短路：【OI Wiki 中链接：[this](https://oi-wiki.org/graph/shortest-path/#dijkstra-%E7%AE%97%E6%B3%95)】 - [P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371) - [P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779) - 单源次短路：[P2865 [USACO06NOV] Roadblocks G](https://www.luogu.com.cn/problem/P2865) - SPFA 判负环：[P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385) - Floyd 算法：[B3647 【模板】Floyd](https://www.luogu.com.cn/problem/B3647)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/shortest-path/#floyd-%E7%AE%97%E6%B3%95)】 - 拓扑排序：[B3644 【模板】拓扑排序 / 家谱树](https://www.luogu.com.cn/problem/B3644)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/topo/)】 - 欧拉路：[P7771 【模板】欧拉路径](https://www.luogu.com.cn/problem/P7771)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/euler/)】 - 二分图的判定：【OI Wiki 中链接：[this](https://oi-wiki.org/graph/bi-graph/#%E5%88%A4%E5%AE%9A)】 - 强联通分量：[B3609 [图论与代数结构 701] 强连通分量](https://www.luogu.com.cn/problem/B3609)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/scc/)】 - 割点：[P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/cut/)】 - 树的重心：[P1395 会议](https://www.luogu.com.cn/problem/P1395)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/tree-centroid/)】 - 树的直径：[B4016 树的直径](https://www.luogu.com.cn/problem/B4016)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/tree-diameter/)】 - 最近公共祖先：[P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/lca/)】 - 树上差分：[P3128 [USACO15DEC] Max Flow P](https://www.luogu.com.cn/problem/P3128)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/prefix-sum/#%E6%A0%91%E4%B8%8A%E5%B7%AE%E5%88%86)】 ### 0x114 动态规划 - 树形动态规划：[P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352)【OI Wiki 中链接：[this](https://oi-wiki.org/dp/tree/)】 - 状态压缩动态规划：[P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896)【OI Wiki 中链接：[this](https://oi-wiki.org/dp/state/)】 - 动态规划常见优化： - 单调队列/单调栈优化：【OI Wiki 中链接：[this](https://oi-wiki.org/dp/opt/monotonous-queue-stack/)】 - 斜率优化：【OI Wiki 中链接：[this](https://oi-wiki.org/dp/opt/slope/)】 - 四边形不等式优化：【OI Wiki 中链接：[this](https://oi-wiki.org/dp/opt/quadrangle/)】 ## 0x12 数学 ### 0x120 数论 【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/basic/)】 - 欧拉函数与欧拉定理：【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/euler-totient/)】 - 费马小定理：【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/fermat/#%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)】 - 威尔逊定理：【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/wilson/)】 - 裴蜀定理：[P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/bezouts/)】 - 模运算意义下的乘法逆元：【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/inverse/)】 - [P3811 【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811) - [P5431 【模板】模意义下的乘法逆元 2](https://www.luogu.com.cn/problem/P5431) - [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)（保证模数是质数） - [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)（不保证模数是质数） - 扩展欧几里得算法：[P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/linear-equation/#%E7%94%A8%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95%E6%B1%82%E8%A7%A3)】 - 中国剩余定理：[P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪](https://www.luogu.com.cn/problem/P1495)【OI Wiki 中链接：[this](https://oi-wiki.org/math/number-theory/crt/)】 ### 0x121 组合数学 【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/combination/)】 - 组合数：【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/combination/#%E7%BB%84%E5%90%88%E6%95%B0)】 - [B3717 组合数问题](https://www.luogu.com.cn/problem/B3717) - [P3807 【模板】卢卡斯定理/Lucas 定理](https://www.luogu.com.cn/problem/P3807) - 错排列：【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/derangement/)】 - 鸽巢原理（抽屉原理）：【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/drawer-principle/)】 - 容斥原理：【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/)】 - 卡特兰数：[P1044 [NOIP2003 普及组] 栈](https://www.luogu.com.cn/problem/P1044)【OI Wiki 中链接：[this](https://oi-wiki.org/math/combinatorics/catalan/)】 ### 0x122 线性代数 【OI Wiki 中链接：[this](https://oi-wiki.org/math/linear-algebra/)】 - 向量及其运算：【OI Wiki 中链接：[this](https://oi-wiki.org/math/linear-algebra/vector/)】 - 矩阵的概念、运算及初等变换：【OI Wiki 中链接：[this](https://oi-wiki.org/math/linear-algebra/matrix/) and [this](https://oi-wiki.org/math/linear-algebra/elementary-operations/)】 - 矩阵快速幂：[P3390 【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390)【OI Wiki 中链接：[this](https://oi-wiki.org/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95)】 - 矩阵加速：[P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962)【OI Wiki 中链接：[this](https://oi-wiki.org/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E5%8A%A0%E9%80%9F%E9%80%92%E6%8E%A8)】 - 高斯消元法：[P3389 【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)【OI Wiki 中链接：[this](https://oi-wiki.org/math/numerical/gauss/)】 # 0x2 提高组（拓展） **这一部分的知识点在 NOI 大纲 - 提高级中未直接出现，但也是提高组选手应当了解的算法，故也收录在本题单。** ## 0x20 数据结构 - 单调栈：[P5788 【模板】单调栈](https://www.luogu.com.cn/problem/P5788)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/monotonous-stack/)】 ## 0x21 图论 - 分层图：[P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/node/#%E5%88%86%E5%B1%82%E5%9B%BE%E6%9C%80%E7%9F%AD%E8%B7%AF)】 - 传递闭包：[B3611 【模板】传递闭包](https://www.luogu.com.cn/problem/B3611)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/shortest-path/#%E5%BA%94%E7%94%A8) 中第二个问题】 - 全源最短路（Johnson 算法）：[P5905 【模板】全源最短路（Johnson）](https://www.luogu.com.cn/problem/P5905)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/shortest-path/#johnson-%E5%85%A8%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E7%AE%97%E6%B3%95)】 - 缩点：[P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387) - 边双联通分量：[P8436 【模板】边双连通分量](https://www.luogu.com.cn/problem/P8436)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/bcc/#%E8%BE%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F)】 - 点双联通分量：[P8435 【模板】点双连通分量](https://www.luogu.com.cn/problem/P8435)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/bcc/#%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F)】 ## 0x22 动态规划 - 数位动态规划：[P2602 [ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602)【OI Wiki 中链接：[this](https://oi-wiki.org/dp/number/)】 ## 0x23 其他 - 反悔贪心：[P2949 [USACO09OPEN] Work Scheduling G](https://www.luogu.com.cn/problem/P2949)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/greedy/#%E5%90%8E%E6%82%94%E8%A7%A3%E6%B3%95)】 - 三分：【OI Wiki 中链接：[this](https://oi-wiki.org/basic/binary/#%E4%B8%89%E5%88%86%E6%B3%95)】 - [P3382 三分](https://www.luogu.com.cn/problem/P3382) - [P1883 【模板】三分 | 函数](https://www.luogu.com.cn/problem/P1883)