OI模板集-提高篇 Part I

此系列：

普及篇
提高篇 Part I
提高篇 Part II

这个题单是个人根据 NOI 大纲 2025 版中的内容以及个人经验所总结出的 OI 中较为模板化的题目。

0x1 提高组（标准）

这一部分只涉及在 NOI 大纲 - 提高级中出现的知识点。

0x10 数据结构

单调队列：P1886 滑动窗口 /【模板】单调队列【OI Wiki link】
ST 表：P3865 【模板】ST 表 && RMQ 问题【OI Wiki link】
并查集：P3367 【模板】并查集【OI Wiki link】
二叉堆：P3378 【模板】堆【OI Wiki link】
树状数组：【OI Wiki link】
- P3374 【模板】树状数组 1
- P3368 【模板】树状数组 2
线段树：【OI Wiki link】
- P3372 【模板】线段树 1
- P3373 【模板】线段树 2
字典树：P8306 【模板】字典树【OI Wiki link】
笛卡尔树：P5854 【模板】笛卡尔树【OI Wiki link】
平衡树：【OI Wiki link】
- P3369 【模板】普通平衡树
- P6136 【模板】普通平衡树（数据加强版）
哈希表：P11615 【模板】哈希表【OI Wiki link】
0x11 算法

0x110 算法策略 & 基础算法
离散化：B3694 数列离散化【OI Wiki link】
扫描线：【OI Wiki link】
- P5490 【模板】扫描线 & 矩形面积并
- P10814 【模板】离线二维数点
分治：【OI Wiki link】
0x111 字符串
KMP 算法：P3375 【模板】KMP【OI Wiki link】
字符串哈希：P3370 【模板】字符串哈希【OI Wiki link】
Manacher 算法：P3805 【模板】Manacher【OI Wiki link】
0x112 搜索
记忆化搜索：【OI Wiki link】
启发式搜索（A*）：P2324 [SCOI2005] 骑士精神【OI Wiki link】
双向搜索：P4799 [CEOI2015 Day2] 世界冰球锦标赛【OI Wiki link】
迭代加深搜索：P1763 埃及分数【OI Wiki link】
0x113 图论
最小生成树：P3366 【模板】最小生成树【OI Wiki link】
次小生成树：P4180 [BJWC2010] 严格次小生成树【OI Wiki link】
单源最短路：【OI Wiki link】
- P3371 【模板】单源最短路径（弱化版）
- P4779 【模板】单源最短路径（标准版）
单源次短路：P2865 [USACO06NOV] Roadblocks G
SPFA 判负环：P3385 【模板】负环
Floyd 算法：B3647 【模板】Floyd【OI Wiki link】
拓扑排序：B3644 【模板】拓扑排序 / 家谱树【OI Wiki link】
欧拉路：P7771 【模板】欧拉路径【OI Wiki link】
二分图的判定：【OI Wiki link】
强联通分量：B3609 [图论与代数结构 701] 强连通分量【OI Wiki link】
割点：P3388 【模板】割点（割顶）【OI Wiki link】
树的重心：P1395 会议【OI Wiki link】
树的直径：B4016 树的直径【OI Wiki link】
最近公共祖先：P3379 【模板】最近公共祖先（LCA）【OI Wiki link】
树上差分：P3128 [USACO15DEC] Max Flow P【OI Wiki link】
0x114 动态规划
树形动态规划：P1352 没有上司的舞会【OI Wiki link】
状态压缩动态规划：P1896 [SCOI2005] 互不侵犯【OI Wiki link】
动态规划常见优化：
- 单调队列/单调栈优化：【OI Wiki link】
- 斜率优化：【OI Wiki link】
- 四边形不等式优化：【OI Wiki link】
  0x12 数学
  
  0x120 数论
  
  【OI Wiki link】
欧拉函数与欧拉定理：【OI Wiki link】
费马小定理：【OI Wiki link】
威尔逊定理：【OI Wiki link】
裴蜀定理：P4549 【模板】裴蜀定理【OI Wiki link】
模运算意义下的乘法逆元：【OI Wiki link】
- P3811 【模板】模意义下的乘法逆元
- P5431 【模板】模意义下的乘法逆元 2
- P2613 【模板】有理数取余（保证模数是质数）
- P1082 [NOIP2012 提高组] 同余方程（不保证模数是质数）
扩展欧几里得算法：P1082 [NOIP2012 提高组] 同余方程【OI Wiki link】
中国剩余定理：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪【OI Wiki link】
0x121 组合数学

【OI Wiki link】
组合数：【OI Wiki link】
- B3717 组合数问题
- P3807 【模板】卢卡斯定理/Lucas 定理
错排列：【OI Wiki link】
鸽巢原理（抽屉原理）：【OI Wiki link】
容斥原理：【OI Wiki link】
卡特兰数：P1044 [NOIP2003 普及组] 栈【OI Wiki link】
0x122 线性代数

【OI Wiki link】
向量及其运算：【OI Wiki link】
矩阵的概念、运算及初等变换：【OI Wiki link，link2】
矩阵快速幂：P3390 【模板】矩阵快速幂【OI Wiki link】
矩阵加速：P1962 斐波那契数列【OI Wiki link】
高斯消元法：P3389 【模板】高斯消元法【OI Wiki link】
0x2 提高组（拓展）

这一部分的知识点在 NOI 大纲 - 提高级中未直接出现，但也是提高组选手应当了解的算法，故也收录在本题单。

0x20 数据结构
单调栈：P5788 【模板】单调栈【OI Wiki link】
0x21 图论
分层图：P4568 [JLOI2011] 飞行路线【OI Wiki link】
传递闭包：B3611 【模板】传递闭包【OI Wiki link 第二个问题】
全源最短路（Johnson 算法）：P5905 【模板】全源最短路（Johnson）【OI Wiki link】
缩点：P3387 【模板】缩点
边双联通分量：P8436 【模板】边双连通分量【OI Wiki link】
点双联通分量：P8435 【模板】点双连通分量【OI Wiki link】
0x22 动态规划
数位动态规划：P2602 [ZJOI2010] 数字计数【OI Wiki link】
0x23 其他
反悔贪心：P2949 [USACO09OPEN] Work Scheduling G【OI Wiki link】
三分：【OI Wiki link】
- P3382 三分
- P1883 【模板】三分 | 函数

OI模板集-提高篇 Part I

0x1 提高组（标准）

0x10 数据结构

0x11 算法

0x110 算法策略 & 基础算法

0x111 字符串

0x112 搜索

0x113 图论

0x114 动态规划

0x12 数学

0x120 数论

0x121 组合数学

0x122 线性代数

0x2 提高组（拓展）

0x20 数据结构

0x21 图论

0x22 动态规划

0x23 其他