【原经典模板汇总】ois 的普及算法训练计划

**原 经典模板题汇总 - 普及算法**。 **** ~~这大概是为数不多的混在前几页各类神仙算法中的一个普及题单之一~~ **这份题单收录了普及组经常涉及的算法的经典题目，帮助普及组选手复习整理算法。通过这个题单，你能了解到普及组都有哪些算法，并获得相关资源。以及，这份题单也能帮助你在考前快速复习学过的所有算法。** 当然，对于每个具体算法还是要多练习。 每个 OIer 心目中的「普及组算法」是有差异的。这份题单只是基于本蒟蒻的经验的，如果你有更好的意见，欢迎私信探讨 qwq **** # 这个题单包含哪些内容 普及组的经典题，包括： - 一些常见算法 - 简单的数学相关问题 - 简单的动态规划 - 搜索类 - 数据结构 **在目录中列出了对算法的简单介绍，并给出了更多资源。** 更名后，本提单将不再囿于每个算法一道“模板题”。有的算法会包含多道题，还会收录一些用到常见技巧的题目。 # 详细目录 ## 数学 - P1601 A+B Problem（高精） **（高精度加法）** - P1303 A\*B Problem **（高精度乘法）** - P2142 高精度减法 - P1480 A/B Problem **（高精度除以低精度）** - P2005 A/B Problem II **（高精度除以高精度）** - P2818 天使的起誓 **（高精度取余）** **「高精度算法」** 大于 $2^{64}$ 的整数不能使用标准数据类型表示，在早期试题中有时会出现此类整数的计算，此时需要使用特定的方法（高精度算法）。 可以用数组模拟整数，数组的每一位代表整数的每一位，这样基本能存下 $10^7$ **位**以内的整数，足够了。 高精度数的计算则是模拟小学时学过的竖式，按十进制位运算。 了解更多，请见 [高精度计算 - OI Wiki](https://oi-wiki.org/math/bignum/)。关于高精度除以低精度，请见 [高精度除法：高精度除以低精度\_NEFU\_kadia的博客-CSDN博客](https://blog.csdn.net/NEFU_kadia/article/details/104214133)。 - P1075 [NOIP2012 普及组] 质因数分解 **（素数 / 质数）** 请参考：[数论基础 - OI Wiki](https://oi-wiki.org/math/number-theory/basic/) 与 [暴力做法 - 素数判定 - 素数 - OI Wiki](https://oi-wiki.org/math/number-theory/prime/#_2)。 - P4994 终于结束的起点 **（斐波那契数列）** - P1002 过河卒 **（二维斐波那契 / 标数法）** - P1044 栈 **（卡特兰数）** 请参考：[斐波那契数列 - OI Wiki](https://oi-wiki.org/math/fibonacci/) 与 [卡特兰数 - OI Wiki](https://oi-wiki.org/math/combinatorics/catalan/)。 - P1226 【模板】快速幂||取余运算 **（整数快速幂）** 请参考：[递归 & 分治 - OI Wiki](https://oi-wiki.org/basic/divide-and-conquer/#_7) 与 [快速幂 - OI Wiki](https://oi-wiki.org/math/quick-pow/)。 - B3619 10 进制转 x 进制 - B3620 x 进制转 10 进制 请参考：[进位制 - OI Wiki](https://oi-wiki.org/math/base/)。 ## 排序 - P1059 明明的随机数 **（桶排）** **「桶排序」** 桶排序是时间复杂度很优的一个排序算法，也是最好写的。 桶排序针对范围不大的一些数，方法是为每个可能的值建立一个「桶」，即数组 `b[]`，`b[i]` 表示取值为 $i$ 的数的个数。 先遍历一遍所有数，在相应的桶记录（`b[a[i]]++;`），然后再顺序遍历一遍桶，一个值有几个数就打印几个数即可。 桶排序的复杂度是 $\mathcal{O}(n)$，打破了基于比较的排序算法的下界。 事实上，刚刚所说的（以及这道模板题需要的）仅仅是一种特殊情况的桶排序。关于“真正的”桶排序，请阅读 [桶排序（箱排序）原理及其时间复杂度详解](http://data.biancheng.net/view/115.html)，以及 [桶排序 - OI Wiki](https://oi-wiki.org/basic/bucket-sort/)。 - P1093 奖学金 **（多关键字排序）** **「多关键字排序」** 利用 C++ STL 的 `sort()` 可以方便实现结构体的排序。 方法一是自定义比较函数。比较函数应是一个返回值为布尔类型的函数，参数为两个该结构体类型的变量。如果传入的第一个结构体「大于」第二个结构体，则返回 `true`，否则返回 `false`。此种方法需要在 `sort()` 里传入一个比较函数的函数指针，形如：`sort(a+1,a+n+1,cmp);`。用这种方法还可以使 `sort()` 从大到小排序整数。关于这种方法，请阅读 [结构体的sort排序 - wushuyng - 博客园](https://www.cnblogs.com/wushengyang/p/10865369.html)。 另一种方法则更为直接，直接重载结构体的小于运算符。这种方法调用 `sort()` 则不需要更改，正常调用即可。关于重载运算符的方法，请阅读 [C++ 重载运算符和重载函数 | 菜鸟教程](https://www.runoob.com/cplusplus/cpp-overloading.html) - P1116 车厢重组 **（冒泡排序）** **「冒泡排序」** 法如其名，在冒泡排序执行过程中，将序列中较小的数会像冒泡一样移动到数列的顶部。冒泡排序执行 $n$ 轮操作，每一轮扫描所有相邻的对象，若当前对象和当前对象之后的对象不满足排序要求，则交换当前对象与当前对象之后的对象。冒泡排序的复杂度是 $\mathcal{O}(n^2)$。 更详细的介绍，详见 [冒泡排序 - OI Wiki](https://oi-wiki.org/basic/bubble-sort/)。 - P1177【模板】快速排序 **（快速排序，归并排序）** **「快速排序」** 快速排序采取的分治的思想，将待排序序列分为两部分，通过交换元素的方式使前一部分中的数小于后一部分中的数，然后递归排序两个部分。 快速排序的复杂度是 $\mathcal{O}(n\log n)$，在其发明时属于较快的算法（现在依然够快），由此得名。快速排序的最坏复杂度是 $\mathcal{O}(n^2)$（由此可见出题人理论上可以构造数据把你卡到平方阶）。 `STL` 中的 `sort()` 的内部实现就是快速排序，但其经过优化，比起裸的快排，效率有显著的提升。 了解更多，请阅读 [快速排序 - OI Wiki](https://oi-wiki.org/basic/quick-sort/)。 **「归并排序」** 同样采用分治思想，归并排序分为两步。 1. **分**：直接将待排序数组一分为二，递归下去继续分。 2. **治**：将两个子数列递归的合并，在合并时对数列进行排序，保证合并后产出的序列是有序的。 了解更多，请见 [归并排序 - OI Wiki](https://oi-wiki.org/basic/merge-sort/)。 - P1908 逆序对 **「逆序对」** 在给定的数列 $a_1,a_2\cdots, a_n$ 中，若对于 $i<j$，有 $a_i>a_j$，则称数对 $(a_i,a_j)$ 为一个逆序对。求逆序对的个数是一个经典问题。 1. 若按照定义求解，复杂度自然是 $\mathcal{O}(n^2)$。 2. 由于冒泡排序的过程实际上就是在不停“消除”逆序对，因此自然想到用冒泡排序来求解逆序对，每次交换时统计数量加一即可。复杂度仍然是 $\mathcal{O}(n^2)$。 3. 归并排序的合并过程实际上也可以用来判断逆序对。详细了解，请见 [逆序对 - 归并排序 - OI Wiki](https://oi-wiki.org/basic/merge-sort/#_2)。 - P1781 宇宙总统 **（字符串排序）** **「字符串排序」** 一般来说，包括本题的字符串的排序问题需要我们按照如下的规则来确定顺序。 1. 长度不一样的，长度长的更大。 2. 长度一样的，从左端开始，依次比较两个字符串相同位置上的字符，$\text{ASCII}$ 值更大的所在的字符串更大。若两个字符一样，则继续比较下一位字符。若两个字符串完全相同，则判为相等。 ## 二分 - P2249 【深基13.例1】查找 **（二分查找）** **「二分查找」** 考虑在一个有序序列中查找一个数的问题。 一个朴素的算法是遍历整个序列，若给定数与当前数相等则输出下标，复杂度为 $\mathcal{O}(n)$。 但是，有复杂度更优的算法。因为序列是有序的，我们将序列正中间的数与给定数比较。若给定数大于此数，因为序列是有序的，所以可以断定要找的数一定在后半段中，反之一定在前半段中。由此递归地处理，每比较一次会排除掉一半的数。因此，最多需要 $\log n$ 次比较，复杂度是 $\mathcal{O}(\log n)$。 了解更多，请见 [二分查找 - 二分 - OI Wiki](https://oi-wiki.org/basic/binary/#_2)。如果你不知道什么是 $\log$，请见 [log2\_百度百科](https://baike.baidu.com/item/log2/2393333)。 - P1024 一元三次方程求解 **（实数域二分）** **「实数域二分」** 如果要在实数域内进行二分查找（比如求一个定义域为非无穷集的函数的零点），也可以利用二分查找，但不像整数，按照「取中间值」的方法是可以无限递归下去的，因此我们可以根据题目的要求设定一个精度 $\varepsilon$（例如 $\varepsilon=0.00001$），如果差小于精度则视为相等，不再递归。 设定精度的方法也是与实数有关的问题中较常见的一种判等方法。 - P2440 木材加工 **（二分答案）** **「二分答案」** 二分法用途较窄，但其背后蕴含的二分思想则是近年竞赛的常考点。一般二分可解决的问题都是极值相关的问题（求某个量的最大/小值），这个时候我们可以二分这个量可能取的范围 $[l,r]$，每次取这个范围的中点 $m=\dfrac{l+r}{2}$ 检测。若检测通过（即这个量可以取这个值），则继续递归尝试区间的后半段；若检测不通过，则更大的数显然不可能，此时递归尝试区间的前半段。需要注意，可以二分答案的题必须满足单调性。 关于二分答案需满足的条件以及更多例子，详见 [二分答案 - 二分 - OI Wiki](https://oi-wiki.org/basic/binary/#_9)。 ## 递归 请参考： [递归 - 递归 & 分治 - OI Wiki](https://oi-wiki.org/basic/divide-and-conquer/#_3) - B2142 求 1+2+3+...+N 的值 **（递归）** ## 前缀和与差分 请参考：[前缀和 - 前缀和 & 差分 - OI Wiki](https://oi-wiki.org/basic/prefix-sum/#_1)。 - B3612 【深进1.例1】求区间和 **（一维前缀和）** ## 贪心 请参考：[贪心 - OI Wiki](https://oi-wiki.org/basic/greedy/)。 - P1803 凌乱的yyy / 线段覆盖 **（线段覆盖）** - P2240 【深基12.例1】部分背包问题 **（部分背包）** ## 栈 请参考：[栈 - OI Wiki](https://oi-wiki.org/ds/stack/) 与 [非递归 - 表达式求值 - OI Wiki](https://oi-wiki.org/misc/expression/#_2)。 - B3614 【模板】栈 - P1449 后缀表达式 **（后缀表达式求值）** - P1981 表达式求值 **（中缀表达式求值）** ## 队列 请参考： [队列 - OI Wiki](https://oi-wiki.org/ds/queue/)。 - B3616 【模板】队列 ## 链表 请参考：[链表 - OI Wiki](https://oi-wiki.org/ds/linked-list/)。 - B3631 单向链表 **（单向链表）** - P1996 约瑟夫问题 **（双向链表）** ## 二叉树 请参见：[树基础 - OI Wiki](https://oi-wiki.org/graph/tree-basic/) 与 [递归 - 表达式求值 - OI Wiki](https://oi-wiki.org/misc/expression/#_1)。 - P1030 求先序排列 **（二叉树）** （以下两道题前面添加过） - P1449 后缀表达式 **（后缀表达式树）** - P1981 表达式求值 **（中缀表达式树）** ## 堆 请参见：[堆简介 - OI Wiki](https://oi-wiki.org/ds/heap/) 与 [二叉堆 - OI Wiki](https://oi-wiki.org/ds/binary-heap/)。 - P3378 【模板】堆 > 想要练习更多，请前往我的数据结构题单：[经典模板汇总 - 提高组数据结构](https://www.luogu.com.cn/training/3367) ## DFS / 回溯 请参见：[DFS（搜索）- OI Wiki](https://oi-wiki.org/search/dfs/)，[回溯法 - OI Wiki](https://oi-wiki.org/search/backtracking/) 与 [记忆化搜索 - OI Wiki](https://oi-wiki.org/dp/memo/) - P1219 [USACO1.5]八皇后 Checker Challenge **（回溯）** - P1706 全排列问题 **（全排列）** - P1028 数的计算 **（记忆化搜索基础）** ## BFS / 连通块 请参见：[BFS（搜索）- OI Wiki](https://oi-wiki.org/search/bfs/)。 - P1443 马的遍历 **（BFS）** - P1451 求细胞数量 **（连通块）** ## 动态规划基础 请参见：[动态规划部分简介 - OI Wiki](https://oi-wiki.org/dp/) - P1048 采药 **（01背包）** 请参见：[0-1 背包 - 背包 DP - OI Wiki](https://oi-wiki.org/dp/knapsack/#0-1)。 - P1616 疯狂的采药 **（完全背包）** 请参见：[完全背包 - 背包 DP - OI Wiki](https://oi-wiki.org/dp/knapsack/#_1)。 - P1757 通天之分组背包 **（分组背包）** 请参见：[分组背包 - 背包 DP - OI Wiki](https://oi-wiki.org/dp/knapsack/#_7)。 - P1064 金明的预算方案 **（有依赖的背包）** 请参见：[有依赖的背包 - 背包 DP - OI Wiki](https://oi-wiki.org/dp/knapsack/#_8)。 关于其他类型的背包问题，请参见 [背包 DP - OI Wiki](https://oi-wiki.org/dp/knapsack/)。 - P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles **（一维动态规划）** - P1434 [SHOI2002]滑雪 **（多维动态规划）** 请参见：[动态规划基础 - OI Wiki](https://oi-wiki.org/dp/basic/)。 - P1854 花店橱窗布置 **（区间 DP）** 请参见：[区间 DP - OI Wiki](https://oi-wiki.org/dp/interval/)。 ## 图论基础 - P1692 部落卫队 **（图的遍历）** - P2910 [USACO08OPEN]Clear And Present Danger S **（Floyd）** > 想要练习更多，请前往我的图论题单：[经典模板汇总 - 提高组图论](https://www.luogu.com.cn/training/3364) # 更新日志 - $2020/04/10$ · P2005 被 **撤下**，原因是 **过于毒瘤，卡常数** - $2020/06/06$ · 增加了一部分知识的说明。 - $2020/09/17$ · P2005 被 **加上**，原因是 **我当时好线性筛啊 >\_<**，顺便更新了一部分。 - $2020/09/19$ · 更名题单，~~经典模板题汇总 - 普及算法~~ $\rightarrow$ ois 的普及算法训练计划。添加了一部分知识的说明。修了排版。 - $2020/09/24$ · 增加了一部分知识的说明。增加了一道 P2440。 - $2022/05/23$ · **大规模更新。** 目录部分增加了相应的知识在 OI Wiki 的链接，并增加了一些来自入门题库的模板题。