返回目录

0x0 前言

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

此题单的优点：

• 紧随 NOI 大纲；
• 选取题目典型、有代表性；
• 附 OI Wiki 链接，供新手学习并深入理解算法。

  0x1 提高组（标准）

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

  0x10 数据结构

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

  0x11 算法

  0x110 算法策略 & 基础算法

• 离散化：B3694 数列离散化【OI Wiki 中链接：this】
• 扫描线：P5490 【模板】扫描线 & 矩形面积并【OI Wiki 中链接：this】
• 分治：【OI Wiki 中链接：this】

  0x111 字符串

• KMP 算法：P3375 【模板】KMP【OI Wiki 中链接：this】
• 字符串哈希：P3370 【模板】字符串哈希【OI Wiki 中链接：this】
• Manacher 算法：P3805 【模板】manacher【OI Wiki 中链接：this】

  0x112 搜索

• 记忆化搜索：【OI Wiki 中链接：this】
• 启发式搜索（A*）：P2324 [SCOI2005] 骑士精神【OI Wiki 中链接：this】
• 双向搜索：P4799 [CEOI2015 Day2] 世界冰球锦标赛【OI Wiki 中链接：this】
• 迭代加深搜索：P1763 埃及分数【OI Wiki 中链接：this】

  0x113 图论

• 最小生成树：P3366 【模板】最小生成树【OI Wiki 中链接：this】
• 次小生成树：P4180 [BJWC2010] 严格次小生成树【OI Wiki 中链接：this】
• 单源最短路：【OI Wiki 中链接：this】
  • P3371 【模板】单源最短路径（弱化版）
  • P4779 【模板】单源最短路径（标准版）
• 单源次短路：P2865 [USACO06NOV] Roadblocks G
• SPFA 判负环：P3385 【模板】负环
• Floyd 算法：B3647 【模板】Floyd【OI Wiki 中链接：this】
• 拓扑排序：B3644 【模板】拓扑排序 / 家谱树【OI Wiki 中链接：this】
• 欧拉路：P7771 【模板】欧拉路径【OI Wiki 中链接：this】
• 二分图的判定：【OI Wiki 中链接：this】
• 强联通分量：B3609 [图论与代数结构 701] 强连通分量【OI Wiki 中链接：this】
• 割点：P3388 【模板】割点（割顶）【OI Wiki 中链接：this】
• 树的重心：P1395 会议【OI Wiki 中链接：this】
• 树的直径：B4016 树的直径【OI Wiki 中链接：this】
• 最近公共祖先：P3379 【模板】最近公共祖先（LCA）【OI Wiki 中链接：this】
• 树上差分：P3128 [USACO15DEC] Max Flow P【OI Wiki 中链接：this】

  0x114 动态规划

• 树形动态规划：P1352 没有上司的舞会【OI Wiki 中链接：this】
• 状态压缩动态规划：P1896 [SCOI2005] 互不侵犯【OI Wiki 中链接：this】
• 动态规划常见优化：
  • 单调队列/单调栈优化：【OI Wiki 中链接：this】
  • 斜率优化：【OI Wiki 中链接：this】
  • 四边形不等式优化：【OI Wiki 中链接：this】

    0x12 数学

    0x120 数论

    【OI Wiki 中链接：this】

• 欧拉函数与欧拉定理：【OI Wiki 中链接：this】
• 费马小定理：【OI Wiki 中链接：this】
• 威尔逊定理：【OI Wiki 中链接：this】
• 裴蜀定理：P4549 【模板】裴蜀定理【OI Wiki 中链接：this】
• 模运算意义下的乘法逆元：【OI Wiki 中链接：this】
  • P3811 【模板】模意义下的乘法逆元
  • P5431 【模板】模意义下的乘法逆元 2
  • P2613 【模板】有理数取余（保证模数是质数）
  • P1082 [NOIP2012 提高组] 同余方程（不保证模数是质数）
• 扩展欧几里得算法：P1082 [NOIP2012 提高组] 同余方程【OI Wiki 中链接：this】
• 中国剩余定理：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪【OI Wiki 中链接：this】

  0x121 组合数学

  【OI Wiki 中链接：this】

• 组合数：【OI Wiki 中链接：this】
  • B3717 组合数问题
  • P3807 【模板】卢卡斯定理/Lucas 定理
• 错排列：【OI Wiki 中链接：this】
• 鸽巢原理（抽屉原理）：【OI Wiki 中链接：this】
• 容斥原理：【OI Wiki 中链接：this】
• 卡特兰数：P1044 [NOIP2003 普及组] 栈【OI Wiki 中链接：this】

  0x122 线性代数

  【OI Wiki 中链接：this】

• 向量及其运算：【OI Wiki 中链接：this】
• 矩阵的概念、运算及初等变换：【OI Wiki 中链接：this and this】
• 矩阵快速幂：P3390 【模板】矩阵快速幂【OI Wiki 中链接：this】
• 矩阵加速：P1962 斐波那契数列【OI Wiki 中链接：this】
• 高斯消元法：P3389 【模板】高斯消元法【OI Wiki 中链接：this】

  0x2 提高组（拓展）

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

  0x20 数据结构

• 单调栈：P5788 【模板】单调栈【OI Wiki 中链接：this】

  0x21 图论

• 分层图：P4568 [JLOI2011] 飞行路线【OI Wiki 中链接：this】
• 传递闭包：B3611 【模板】传递闭包【OI Wiki 中链接：this 中第二个问题】
• 全源最短路（Johnson 算法）：P5905 【模板】全源最短路（Johnson）【OI Wiki 中链接：this】
• 缩点：P3387 【模板】缩点
• 边双联通分量：P8436 【模板】边双连通分量【OI Wiki 中链接：this】
• 点双联通分量：P8435 【模板】点双连通分量【OI Wiki 中链接：this】

  0x22 动态规划

• 数位动态规划：P2602 [ZJOI2010] 数字计数【OI Wiki 中链接：this】

  0x23 其他

• 反悔贪心：P2949 [USACO09OPEN] Work Scheduling G【OI Wiki 中链接：this】
• 三分：【OI Wiki 中链接：this】
  • P3382 三分
  • P1883 【模板】三分 | 函数

1. P1886 - 【模板】单调队列 / 滑动窗口
2. P3865 - 【模板】ST 表 & RMQ 问题
3. P3367 - 【模板】并查集
4. P3378 - 【模板】堆
5. P3374 - 【模板】树状数组 1
6. P3368 - 【模板】树状数组 2
7. P3372 - 【模板】线段树 1
8. P3373 - 【模板】线段树 2
9. P8306 - 【模板】字典树 / Trie
10. P5854 - 【模板】笛卡尔树
11. P3369 - 【模板】普通平衡树
12. P6136 - 【模板】普通平衡树（数据加强版）
13. P11615 - 【模板】哈希表
14. B3694 - 【模板】数列离散化
15. P5490 - 【模板】扫描线 & 矩形面积并
16. P3375 - 【模板】KMP
17. P3370 - 【模板】字符串哈希
18. P3805 - 【模板】Manacher
19. P2324 - [SCOI2005] 骑士精神
20. P4799 - [CEOI 2015] 世界冰球锦标赛 (Day2)
21. P1763 - 埃及分数
22. P3366 - 【模板】最小生成树
23. P4180 - [BJWC2010] 严格次小生成树
24. P3371 - 【模板】单源最短路径（弱化版）
25. P4779 - 【模板】单源最短路径（标准版）
26. P2865 - [USACO06NOV] Roadblocks G
27. P3385 - 【模板】负环
28. B3647 - 【模板】Floyd
29. B3644 - 【模板】拓扑排序 / 家谱树
30. P7771 - 【模板】欧拉路径
31. B3609 - [图论与代数结构 701] 强连通分量
32. P3388 - 【模板】割点（割顶）
33. P1395 - 会议
34. B4016 - 树的直径
35. P3379 - 【模板】最近公共祖先（LCA）
36. P3128 - [USACO15DEC] Max Flow P
37. P1352 - 没有上司的舞会
38. P1896 - [SCOI2005] 互不侵犯
39. P4549 - 【模板】裴蜀定理
40. P3811 - 【模板】模意义下的乘法逆元
41. P5431 - 【模板】模意义下的乘法逆元 2
42. P2613 - 【模板】有理数取余
43. P1082 - [NOIP 2012 提高组] 同余方程
44. P1495 - 【模板】中国剩余定理（CRT）/ 曹冲养猪
45. B3717 - 组合数问题
46. P3807 - 【模板】卢卡斯定理 / Lucas 定理
47. P1044 - [NOIP 2003 普及组] 栈
48. P3390 - 【模板】矩阵快速幂
49. P1962 - 斐波那契数列
50. P3389 - 【模板】高斯消元法