0.简介

本文介绍竞赛中最基本的算法：模拟，枚举，递归，贪心，分治，二分/三分。

其中，模拟和枚举是最基本的。它甚至可以说不是一个算法，而是考察选手的思维逻辑能力和代码实现能力。所以对于这一部分，本文不做讲解。读者可以从各大OJ寻找模拟题进行训练。值得注意的是，模拟题虽然只考察语法，但是它的实现难度未必简单。如著名的斗地主、猪国杀等等。

接下来我们介绍后面的四个基础算法。

1.递归

1.1 概念

递归是计算机科学中的一个重要概念。不仅仅在算法中经常使用，在我们进行计算机相关其他学科的学习时（甚至一些数学定义，如自然数的定义），一些定义或者结构都可能采取递归的方式。一个有趣的例子。

在算法竞赛中，一个函数直接或间接调用自己本身，则其称为递归函数。由此可见，递归函数必须有一个结束条件，否则该函数就会无穷无尽的调用下去了。

1.2 例题

1.2.1 最大公约数

我们知道，求解两个数的最大公约数有两种办法，一种是辗转相除法，另一种是更相减损法。两者的实现原理相同，所以我们只取其一来进行演示。如果你还不会上述办法的话，请自行百度。（算了还是帮你百度一下吧）

在辗转相除法的过程中，我们可以列出如下算式： gcd(a,b)=gcd(b,a\%b) 。当 b=0 时， a 即为原数的最大公约数。

于是一个简单的递归函数就写好了：

在上述函数中， gcd() 函数内部调用了自己，这样的过程就叫做递归（或者说计算到终止时返回的操作就是递归，大概理解就好）。

1.2.2 汉诺塔

递归可以用来解决一些看似规模很大的问题，如汉诺塔问题：

汉诺塔问题是一款经典的益智游戏。它的要求是：给你三根柱子编号为 ABC 。在 A 号柱子上有 n 个大小不同的圆盘，其中大圆盘总在小圆盘上面（我们可以给圆盘编号 1\sim n）。我们的目标是：每次移动一个圆盘，且大圆盘不能在小圆盘之上，使得所有圆盘移动到另一根柱子上。

我们可以用递归的思想：

如果想得到目标状态，考虑第 n 个圆盘，想把它放在另一根柱子上（比如柱 C ），就必须将它上面的 n-1 个圆盘放在柱 B 上。

如果想得到 n-1 个圆盘放在柱 B 上，就要将除 n-1号圆盘的 n-2 个圆盘放到柱 C 上。

以此类推，我们就可以得出解。

举个例子：（手绘）。

所以代码如下：

1.2.3 洛谷P1928 外星密码

对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式（D 是一个整数且 1≤D≤99），比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”，类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2CB]]]”则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。

输入： AC[3FUN] 输出： ACFUNFUNFUN

对于此题，我们需要在读入的时候进行递归。一个字符一个字符读入，如果读到”[“，则记录下一个整数，然后再次调用该读入函数，直到读入”]”为止。来看代码：

2.贪心

2.1 概念

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（较优解）的解题方法。

贪心策略总是做出在 当前看来 是最优的选择。也就是说，贪心并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解。所以我们在利用贪心算法解决问题时往往要证明该题目使用该贪心算法是正确的。（实际上，在具体问题中，我们如果能猜测一道题使用贪心是正确的，或使用贪心能获得较优解即可使用贪心。但 ACM 竞赛中没有部分分的概念，所以如果我们不能确定该题使用贪心算法一定是正确的话，还是要谨慎使用。）

一般来说，一个问题使用贪心算法是一定要证明该贪心算法是正确的。一般采用的策略是假设存在最优解，然后证明贪心得到的解就是最优解或比贪心得到的解更优的解不存在。但还是如上文所说，真正在赛场上实现算法时，严谨的证明还是不需要的。

2.2 例题

2.2.1找零问题

一个小孩用1美元来买价值不足1美元的糖果，售货员希望用数量最少的硬币找给小孩零钱。假设售货员只有14美分、12美分、5美分和1美分的硬币。

1）设计贪心算法来解决找零问题（描述算法的贪心策略并给出算法伪代码）。

2）所设计的贪心算法能保证得到最优解吗？证明你所给的结论。

解：1）设计的贪心算法如下：

假设需要找 x(0 \leq x \leq 100) 美分。先用 14 美分的硬币找零，即找零 n_{14}=\lfloor \frac x {14} \rfloor 枚 14 美分的硬币；再用 12 美分的硬币找零，即找零 n_{12}=\lfloor \frac{(x-14\times n_{14})} {12} \rfloor 枚 12 美分的硬币；然后用 5 美分的硬币找零，即找零 n_5=\lfloor \frac{(x-14\times n_{14}-12\times n_{12})} 5 \rfloor 枚 5 美分的硬币；最后用 1 美分的硬币找零，即找零 n_1=(x-14\times n_{14}-12\times n_{12}-5\times n_5) 枚 1 美分的硬币。最终答案为：找零 n_{14} 枚 14 美分、 n_{12} 枚 12 美分、 n_5 枚 5 美分和 n_1 枚 1 美分的硬币满足题意。

实例代码：

2）证明上述贪心算法：

假设上述算法得到的不是最优解，则一定存在一个最优解记为{n_{14}’枚14美分硬币、n_{12}’枚12美分硬币、n_{5}’枚5美分硬币、n_{1}’枚1美分硬币}，使得n_{14}’+n_{12}’+n_{5}’+n_{1}’。

因为两个解都是可行解，所以有14\times n_{14}’+12\times n_{12}’+5\times n_{5}’+n_{1}’ = 14\times n_{14}+12\times n_{12}+5\times n_{5}+n_{1}.

因为n_{14}为需要找零x美分的情况下最大能找的14美分硬币数，所以n_{14}’ \leq n_{14}.

假设n_{14}'<n_{14}，则说明有若干个14美分需要由剩下的三种硬币找零。每14美分可以由1枚12美分+2枚1美分或2枚5美分+4枚1美分或14枚1美分找零，均大于1枚硬币。因此这种假设得到的不可能是最优解。

所以n_{14}’=n_{14}.

因此问题转化为用12美分、5美分、1美分硬币找零0\leq x-14\times n_{14}<14美分的子问题。

子问题证明思路同上，所以有n_{12}’=n_{12},n_{5}’=n_{5},n_{1}’=n_{1}.

所以n_{14}’+n_{12}’+n_{5}’+n_{1}’ = n_{14}+n_{12}+n_{5}+n_{1}，即上述贪心算法得到的就是最优解。

2.2.2 洛谷P1190 [NOIP2010 普及组] 接水问题

题目链接

贪心策略很简单：下一名接水的同学一定是去目前所有正在接水的同学中最早接完的那里。

这样时间复杂度会不会有一点高？有没有优化的办法呢？

2.2.3 洛谷P1842 [USACO05NOV] 奶牛玩杂技

题目链接

我们要求总压扁指数最小，那么我们就要考虑压扁指数和什么有关？

它和自己的力量有关，和别人的体重有关。

但是换种思路来向，这头奶牛的体重又会影响别人的压扁指数。所以从整体上来看应该是体重和力量的一个关系决定了奶牛的排序。

我们取相邻的奶牛 a,b 。易证这两头奶牛的顺序不会影响其他奶牛的压扁指数。

假设 W_a+S_a<W_b+S_b 。设这两头奶牛上面的所有奶牛的体重和为 W 。

第一种情况，如果 a 在 b 上面，则 a 的压扁指数为 W-S_a ， b 的压扁指数为 W+W_a-S_b ；

第二种情况，如果 b 在 a 上面，则 a 的压扁指数为 W+W_b-S_a ， b 的压扁指数为 W-S_b 。易证这种情况的总压扁指数为 W+W_b-S_a （不考虑其他奶牛的压扁指数）。

该值一定大于第一种情况中的 W-S_a 。再将其与 W+W_a-S_b 做比较，易证 W+W_b-S_a 大。

所以，在 W_a+S_a<W_b+S_b 的情况下， b 在 a 上面会取得更大的总压扁指数。因此我们应该使 a 在 b 上面。

综上，我们只需按 W+S 排序，较小的在上，较大的在下即可满足题意。

3.分治

3.1 概念

分治，分而治之。也是一种算法设计的基本思路。它的思想是将一个问题分解成若干个规模更小的子问题。子问题和原问题相同，只是规模更小。原问题的解可以通过子问题的解来得到。

由此可见，分治的实现往往会用到递归。我们把一个问题拆成子问题，再用子问题得到原问题的解的过程，基本可以类比递归的过程。

不过，分治的思想很重要，它使用递归，又不等同于递归。我们在思考问题时，可以深度理解分治的精髓。

3.2 例题

3.2.1 快速幂

在我们做一些数学题时，往往会用到求一个数的高次幂。

如果这个高次达到 1e5 ，且题目可能不只求一次（可能是 n 次），这样我们就要想一个办法使得我们不用一个一个乘。

我们考虑平时在计算一个数的高次幂时，如我们计算 2^8 ，我们当然可以 2*2*2*2*2*2*2*2 ，但是我们还可以 2^8=4^4=16^2=256 。这样一个过程使得我们计算乘法的次数降低了。当指数更大时，这个降低是很必要的（复杂度会从 O(n) 到 O(logn)）。

于是我们就有了求一个数的高次幂的办法：

假设我们要求 a^n，如果 n 为偶数，我们可以将其化为 (a^2)^{\frac n2} ；如果 n 为奇数，我们可以将其化为 (a^2)^{\frac {n-1}2}*a 。

之后，我们可以按照这种思维继续化简，直至 n=0 。

3.2.2 洛谷P1228 地毯填补问题

对于这个问题，如果我们硬搜每一种可能的情况，时间一定会爆炸。

那么如何分治的思考这个问题呢？

我们可以采取如下步骤：

①因为迷宫大小为 2^k \times 2^k ，那么我们可以将迷宫分为四等分，每个小迷宫大小为2^{(k-1)} × 2^{(k-1)}。

②因为大迷宫中有且仅有一个残缺方格，则该方格必定出现在任意一个小迷宫中。四个小迷宫在大迷宫中对应的中心位置分别是(2^{k-1},2^{k-1});(2^{k-1},2^{k-1}+1);(2^{k-1}+1,2^{k-1});(2^{k-1}+1,2^{k-1}+1)。用一个三格板填充除残缺方格在的另三个小迷宫。则四个小迷宫均变成残缺迷宫。

③重复步骤①，直到迷宫大小为2 × 2，直接用三格板填充即可。

这样，我们就通过把一个大问题分解成四个问题相同，规模更小的子问题，直到到最基本的问题即 2 \times 2 大小的迷宫。

3.2.3 洛谷P1908 逆序对

如何对一个数组排序？我们有很多种办法，如插入排序、冒泡排序、选择排序、快速排序等等。

今天我们讨论的是所有排序方法中，最为稳定的，速度又较快的一种方法：归并排序。

它的实现方法如下：

假设我们要对数组 [11,2,8,3,6,15,12,0,7,4,1,13,5,9,14,10] 排序，则：

我们将其分为两部分分别排序，再将排好序的两部分进行合并。

因为两部分都是有序的，所以合并只需从两个队伍的队首进行遍历，哪边更小则取哪边。

对于分开的两部分，我们可以再将其划分，即分别分成两部分，以此类推，直至划分到单个数。

初始段    [11] [2] [8] [3] [6] [15] [12] [0] [7] [4] [1] [13] [5] [9] [14] [10]

第一步 [2    11] [3   8] [6    15] [0   12] [4    7] [1   13] [5    9] [10   14]

第二步 [2    3    8  11] [0    6    12   15] [1    4   7   13] [5    9   10   14]

第三步 [0    2    3    6   8   11   12   15] [1    4    5   7    9   10   13   14]

第四步 [0    1    2    3   4     5     6     7   8     9   10  11  12  13  14  15]

而求逆序对，我们要明白这样一个定理：逆序对是指两个元素的相对位置。即我们只需要在两部分合并时进行逆序对的计数就可。

用上述的数列举例：归并排序步骤如下：

初始段    [11] [2] [8] [3] [6] [15] [12] [0] [7] [4] [1] [13] [5] [9] [14] [10]

归并到b [2    11] [3   8] [6    15] [0   12] [4    7] [1   13] [5    9] [10   14]
逆序对数：(1+1+1+1+1)=5

复制到a [2    11] [3   8] [6    15] [0   12] [4    7] [1   13] [5    9] [10   14]

归并到b [2    3    8  11] [0    6    12   15] [1    4   7   13] [5    9   10   14]
逆序对数：5+(2+3+2)=12

复制到a [2    3    8  11] [0    6    12   15] [1    4   7   13] [5    9   10   14]

归并到b [0    2    3    6   8   11   12   15] [1    4    5   7    9   10   13   14]
逆序对数：12+(6+4)=22

复制到a [0    2    3    6   8   11   12   15] [1    4    5   7    9   10   13   14]

归并到b [0    1    2    3   4     5     6     7   8     9   10  11  12  13  14  15]
逆序对数：22+29=51

复制到a [0    1    2    3   4     5     6     7   8     9   10  11  12  13  14  15]

这样，我们就可以在归并排序的过程中顺便将逆序对求出。

4.二分

4.1 概念

二分可以理解为在一个单调的序列中寻找答案，每次取序列的中点，根据条件进行取舍。因为序列单调，每次可以舍去一半的序列，因此效率较高。

二分可以分为二分查找和二分答案。前者是正向解题求出答案，后者是反向猜答案验证是否满足。

二分的过程一定要注意区间端点的取舍问题。伪代码如下：

4.2 例题

4.2.1 洛谷P1571 眼红的Medusa