OI模板集-普及篇

[返回目录](https://www.luogu.com.cn/training/428352) # 0x0 前言 这个题单是个人根据 NOI 大纲 2025 版中的内容以及个人经验所总结出的 OI 中较为模板化的题目。 此题单的优点： - 紧随 NOI 大纲； - 选取题目典型、有代表性； - 附 OI Wiki 链接，供新手学习并深入理解算法。 # 0x1 普及组（标准） **这一部分只涉及在 NOI 大纲 - 入门级中出现的知识点。** ## 0x10 数据结构 - 栈：[B3614 【模板】栈](https://www.luogu.com.cn/problem/B3614)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/stack/)】 - 队列：[B3616 【模板】队列](https://www.luogu.com.cn/problem/B3616)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/queue/)】 - 单向链表：[B3631 单向链表](https://www.luogu.com.cn/problem/B3631)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/linked-list/)】 - 双向链表：[P1160 队列安排](https://www.luogu.com.cn/problem/P1160)【OI Wiki 中链接：[this](https://oi-wiki.org/ds/linked-list/)】 - 二叉树：[P1305 新二叉树](https://www.luogu.com.cn/problem/P1305)【OI Wiki 中链接：[this](https://oi-wiki.org/graph/tree-basic/)】 ## 0x11 算法 ### 0x110 基础 - 二分查找：[P2249 【深基13.例1】查找](https://www.luogu.com.cn/problem/P2249)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/binary/)】 - 普通二分答案：[B3628 机器猫斗恶龙](https://www.luogu.com.cn/problem/B3628)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/binary/)】 - 实数域二分答案：[P1577 切绳子](https://www.luogu.com.cn/problem/P1577)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/binary/)】 - 贪心：[P2240 【深基12.例1】部分背包问题](https://www.luogu.com.cn/problem/P2240)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/greedy/)】 - 排序：[P1177 【模板】排序](https://www.luogu.com.cn/problem/P1177)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/sort-intro/)】 ### 0x111 高精度 【OI Wiki 中链接：[this](https://oi-wiki.org/math/bignum/)】 - 加法：[P1601 A+B Problem（高精）](https://www.luogu.com.cn/problem/P1601) - 减法：[P2142 高精度减法](https://www.luogu.com.cn/problem/P2142) - 乘法：[P1303 A*B Problem](https://www.luogu.com.cn/problem/P1303) - 高精除低精：[P1480 A/B Problem](https://www.luogu.com.cn/problem/P1480) ### 0x112 搜索 #### 0x1120 深搜 【OI Wiki 中链接：[this](https://oi-wiki.org/search/dfs/)】 - 经典迷宫：[B3625 迷宫寻路](https://www.luogu.com.cn/problem/B3625) - 求联通块数量：[P1596 [USACO10OCT] Lake Counting S](https://www.luogu.com.cn/problem/P1596) - 泛洪：[P1506 拯救oibh总部](https://www.luogu.com.cn/problem/P1506) #### 0x1121 广搜（深搜会 T） 【OI Wiki 中链接：[this](https://oi-wiki.org/search/bfs/)】 - 经典迷宫-最短路：[P1746 离开中山路](https://www.luogu.com.cn/problem/P1746) ### 0x113 动态规划 【OI Wiki 中链接：[this](https://oi-wiki.org/dp/)】 #### 0x1130 背包类型 【OI Wiki 中链接：[this](https://oi-wiki.org/dp/knapsack/)】 - 01 背包：[P1048 [NOIP2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048) - 二维 01 背包：[P1507 NASA的食物计划](https://www.luogu.com.cn/problem/P1507) - 完全背包：[P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616) - 混合背包（含多重背包，因为洛谷里面没有不用优化的纯多重背包题）：[P1833 樱花](https://www.luogu.com.cn/problem/P1833) - 多重背包二进制优化：[P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) - 分组背包：[P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757) - 有依赖的背包：[P1064 [NOIP2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064) #### 0x1131 区间类型 【OI Wiki 中链接：[this](https://oi-wiki.org/dp/interval/)】 - 标准区间 DP：[P1775 石子合并（弱化版）](https://www.luogu.com.cn/problem/P1775) - 断环为链的区间 DP：[P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) ### 0x114 图论 - 图的存储和 DFS、BFS：[P5318 【深基18.例3】查找文献](https://www.luogu.com.cn/problem/P5318) ### 0x115 数学 【OI Wiki 中链接：[this](https://oi-wiki.org/math/)】 - 质因数分解：[B3715 分解质因子 2](https://www.luogu.com.cn/problem/B3715) - 辗转相除法求 gcd 和 lcm：[B3634 最大公约数和最小公倍数](https://www.luogu.com.cn/problem/B3634) - 线性筛素数：[P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383) ### 0x116 算法策略 - 前缀和：[B3612 【深进1.例1】求区间和](https://www.luogu.com.cn/problem/B3612)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/prefix-sum/)】 - 差分：[P2367 语文成绩](https://www.luogu.com.cn/problem/P2367)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/prefix-sum/#%E5%B7%AE%E5%88%86)】 # 0x2 普及组（拓展） **这一部分的知识点在 NOI 大纲 - 入门级中未直接出现，但也是普及组选手应当了解的算法，故也收录在本题单。** - 快读：[P10815 【模板】快速读入](https://www.luogu.com.cn/problem/P10815) - 快速幂：[P1226 【模板】快速幂](https://www.luogu.com.cn/problem/P1226)【OI Wiki 中链接：[this](https://oi-wiki.org/math/binary-exponentiation/)】 - 二维前缀和、二维差分：[P13787 地毯 加强版](https://www.luogu.com.cn/problem/P13787)【OI Wiki 中链接：[this](https://oi-wiki.org/basic/prefix-sum/#%E4%BA%8C%E7%BB%B4%E5%A4%9A%E7%BB%B4%E5%89%8D%E7%BC%80%E5%92%8C)、[this](https://oi-wiki.org/basic/prefix-sum/#%E4%BA%8C%E7%BB%B4%E5%A4%9A%E7%BB%B4%E5%B7%AE%E5%88%86)】