本文中将涉及一个新的专用术语——合法。这里的合法指的并非“符合法律”，而是“符合规则、符合条件”之意。之后我们提到“合法”一词，也都是这个意思。我们已经学习过了暴力枚举算法——枚举出所有可能的情况，然后判断或者统计，从而解决问题。然而，枚举全部元素的效率如同愚公移山，无法应对数据范围稍大的情形，有时甚至连编写代码都很困难。此时，我们就需要引入一个新的算法了——搜索。此搜索非彼搜索，与百度等联网搜索引擎无关。洛谷 B3621。$n$ 元组是指由 $n$ 个元素组成的序列。例如 $(1,1,2)$ 是一个三元组、$(233,254,277,123)$ 是一个四元组。给定 $n$ 和 $k$，请按字典序输出全体 $n$ 元组，其中元组内的元素是在 $[1, k]$ 之间的整数。$1 \le n\leq 5, 1 \le k\leq 4$。字典序是指优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。看到这题，我们肯定会有一个最朴素的想法是：写 $k$ 层 for 循环，直接枚举所有可能的元组。代码可能是这样的：#include <iostream> using namespace std; int n, m; int main() { cin >> n >> m; if (n == 1) for (int i = 1; i <= m; i++) cout << i << '\n'; else if (n == 2) for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) cout << i << ' ' << j << '\n'; else if (n == 3) for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= m; k++) cout << i << ' ' << j << ' ' << k << '\n'; else if (n == 4) for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= m; k++) for (int g = 1; g <= m; g++) cout << i << ' ' << j << ' ' << k << ' ' << g << '\n'; else for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= m; k++) for (int g = 1; g <= m; g++) for (int h = 1; h <= m; h++) cout << i << ' ' << j << ' ' << k << ' ' << g << ' ' << h << '\n'; return 0; }太丑陋了。另外，我们发现这里的 $k$ 不是固定值，因此如果直接使用循环的话，我们需要对每一个 $k$ 都写 $k$ 层 for 循环。当 $k$ 更大一些的时候，编写代码将变得十分繁琐。我们需要一个更加优秀的算法。传统枚举中，需要固定 for 循环的层数，这样的后果就是程序非常丑陋冗长，而且不能随意增减枚举层数。所以我们介绍一种新的基于递归的枚举算法，枚举每一个填空中所有可能的选项，然后判断这种选项是否合法。如果合法就继续填写下一个选项，然后继续；如果这个填空中的所有选项都不合法，那就不用继续枚举下去了，而是尝试更换上一个填空的选项，继续枚举。这种方式被形象地称为回溯（Backtracking）算法，常使用深度优先搜索（Depth-First Search, DFS）来实现。这种如果已经不合法就不再继续往下递归的过程也被形象地称为剪枝（Pruning）。我们先给出 DFS 的一般形式。void dfs(int k) { // k 代表递归层数，或者说要填第几个空 if (所有空已经填完了) { 判断最优解 / 记录答案; return; } for (枚举这个空能填的选项) { if (这个选项不合法) continue; 记录下这个空（保存现场）; dfs(k + 1); 取消这个空（恢复现场）; } }基于这样的算法，我们给出本题的代码：#include <iostream> using namespace std; const int N = 10; int n, k, a[N]; void dfs(int pos) { // 需要填第 pos 位 if (pos > n) { // 当 n 位都已经填完时终止递归 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; // 填完就输出 cout << '\n'; return; } for (int i = 1; i <= k; ++i) { a[pos] = i; // 将第 pos 位填入 i dfs(pos + 1); // 继续填第 pos + 1 位 } } int main() { cin >> n >> k; solve(1); // 从第 1 位开始填 return 0; }因为本题没有限制条件（每个空都可以填从 $1$ 到 $n$ 的任何数），每个空填的数都与之前填过的数无关，所以我们不需要记录填了什么，自然也就不需要回溯了。当 $n = 2, k = 3$ 时，我们来看看上面这份代码的具体运行过程。进入第 $1$ 层 dfs 函数，$pos = 1$。要枚举第 $1$ 个位置的数字，先从 $1$ 开始，填入 $1$。继续递归 dfs(2)。进入第 $2$ 层 dfs 函数，$pos = 2$。要枚举第 $2$ 个位置的数字，先从 $1$ 开始，填入 $1$。继续递归 dfs(3)。进入第 $3$ 层 dfs 函数，$pos = 3$。要枚举第 $3$ 个位置的数字。先从 $1$ 开始，填入 $1$。继续递归 dfs(4)。进入第 $4$ 层 dfs 函数，发现 $pos = 4$，意味着所有位置已经填写完毕，得到了一个合法的解，因此输出，然后返回上一层，也就是在 dfs(3) 中继续枚举 $2$、$3$，枚举完毕后就再返回上一层 dfs(2)，继续往后枚举。为什么返回上一层还能继续枚举呢？这是因为计算机运行函数时，为每一个子函数都分配了一片栈空间（Stack Space），专门用于存储每一层递归函数的信息，当然就包括每层函数的各个局部变量的值了。这样一来，即使 $n$ 和 $k$ 是变化的，我们也可以只用简单的一个函数搞定了。洛谷 B3623。有 $n$ 个元素，要求按字典序输出所有长度为 $k$ 的排列。$1 \le k \le n \le 10$。排列是从 $n$ 个不同元素中选取 $k$ 个元素（$k \le n$），并按特定顺序进行安排的有序序列。本题要求我们枚举排列，这就意味着不能有重复的元素。也就是说，当前这个空可以填什么，取决于我们之前填过了什么。我们可以开一个 bool 数组 $vis$，用来记录之前哪些元素已经填过了，哪些没填过。枚举这个位置可以填的数时，如果发现这个数之前已经填过了，那么就直接 continue，也就是不填这个数。在填入这个数之后，我们需要也把它标记为“已经填过”，然后继续填下一个位置（进入下一层递归）。下一层递归和之后的递归全部结束之后，要重新标记回“未填过”的状态，这样就不会影响接下来的填写了。#include <iostream> using namespace std; const int N = 15; int n, k, a[N]; bool vis[N]; void dfs(int pos) { // 需要填第 pos 位 if (pos > k) { // 当 n 位都已经填完时终止递归 for (int i = 1; i <= k; ++i) cout << a[i] << ' '; // 填完就输出 cout << '\n'; return; } for (int i = 1; i <= n; ++i) { if (vis[i]) continue; a[pos] = i; // 将第 pos 位填入 i vis[i] = true; // 将 i 标记为已填过 dfs(pos + 1); // 继续填第 pos + 1 位 vis[i] = false; // 取消标记（即标记为未填过） } } int main() { cin >> n >> k; dfs(1); // 从第 1 位开始填 return 0; }当 $n = 3, k = 2$ 时，来看看这份代码的具体运行过程。进入第 $1$ 层 dfs 函数，$pos = 1$。要枚举第 $1$ 个位置的数字，先从 $1$ 开始，填入 $1$。继续递归 dfs(2)。进入第 $2$ 层 dfs 函数，$pos = 2$。要枚举第 $2$ 个位置的数字，先从 $1$ 开始。发现 $1$ 已经被填过了，跳过，然后填入 $2$。继续递归 dfs(3)。进入第 $3$ 层 dfs 函数，发现 $pos = 3$，意味着所有位置已经填写完毕，得到了一个合法的解，因此输出，然后返回上一层，也就是在 dfs(2) 中继续枚举 $3$，枚举完毕后就再返回上一层 dfs(1)，继续往后枚举。似乎和上一道题的枚举过程查不多，只是多了一个判断是否重复的过程。事实也确实如此，搜索的枚举过程大同小异，只是“枚举哪些东西”“判断合法性”和“枚举完毕之后做的事”上略有区别。接下来我们来讨论一些更为复杂的情况。讨论一种简化过的数独游戏——四阶数独。给出一个 $4 \times 4$ 的格子，每个格子都只能填写 $1$ 到 $4$ 的整数，要求每行、每列和四等分更小的正方形部分都刚好由 $1$ 到 $4$ 组成。下图给出了一个合法的四阶数独的例子。给出空白的方格，问一共有多少种合法的填写方案。输出每一种方案，并在程序最后输出总的方案数。回想枚举算法，最朴素的枚举方式是使用 $16$ 层 for 循环，一共要枚举 $4^{16} \approx 4 \times 10^9$ 种情况。现代计算机每秒约可处理 $10^7$ 次运算，显然远低于我们需要枚举的情况数量，不可行。我们之前还讨论过枚举序列。既然每一行都是 $1$ 到 $4$，假设各行都是独立的，分别枚举 $4$ 个 $1$ 到 $4$ 的全排列，组成一个 $4 \times 4$ 的矩阵，然后判断这个矩阵是否符合数独的要求。我们使用类似计数排序的思路判断是否符合要求，也就是记录第 $i$ 行是否有 $1$、$2$、$3$、$4$，如果每个数字刚好都有一个，则说明这一行符合要求；列和小块同理。最多可能有 $(4 \times 3 \times 2 \times 1)^4 \approx 3 \times 10^5$ 种情况，完全可以在一秒钟内运行出结果。然而，这样的解法仍然有很多浪费：如果第一行是 $\{1, 2, 3, 4\}$，第二行第一列是 $1$，后面不管怎么填写，都不符合要求，但还是要继续进行无谓的枚举然后判断。我们希望可以有一个算法，在枚举序列的时候，一旦发现某位数字不符合要求，就立刻中断这种情况的枚举，直接枚举下一情况。这样可以在很大程度上节约程序的运行时间。现在你学过搜索了，问题就变得简单很多了。我们给出这道题的代码：#include <iostream> using namespace std; const int N = 5; int a[N * N], n = 4 * 4, ans; // 全局变量不赋值默认初始化为 0 bool b1[N][N], b2[N][N], b3[N][N]; // 分别记录横行，竖行，四个小块 void dfs(int x) { // 第 x 个空填什么 if (x > n) { // 如果所有空已经填满 ++ans; // 增加结果数量 for (int i = 1; i <= n; ++i) { // 输出放置方案 cout << a[i] << ' '; if (i % 4 == 0) cout << '\n'; // 每输出四个元素就换行一次 } return; } int row = (x - 1) / 4 + 1; // 横行编号 int col = (x - 1) % 4 + 1; // 竖行编号 int block = (row - 1) / 2 * 2 + (col - 1) / 2 + 1; // 小块编号 for (int i = 1; i <= 4; ++i) { if (b1[row][i] || b2[col][i] || b3[col][i]) continue; // 如果已经出现过就跳过 a[x] = i; // 记录放置位置 b1[row][i] = true, b2[col][i] = true, b3[block][i] = true; // 标记为已经出现过 dfs(x + 1); // 下一层递归 b1[row][i] = false, b2[col][i] = false, b3[block][i] = false; // 取消标记 } } int main() { dfs(1); // 从第 1 个空开始枚举 cout << ans << '\n'; return 0; }如何保证放置的位置合法呢？我们使用数组 $b1$、$b2$、$b3$ 来记录横行、竖行、四个小块中的每个数字 $i$ 是否被占用。如果都没有被占用，说明可以填入。把这些空格编号为 $1$ 到 $16$，每个格子所占的行号、列号和小块编号就都可以计算出来了。对于这份代码，它的搜索和回溯的详细步骤如下：进入第 $1$ 层 dfs 函数，$x = 1$。要枚举第 $1$ 个格子的数字，先从 $1$ 开始。这里填 $1$ 没有问题，就把 $1$ 记录下来，同时需要记录第 $1$ 行、第 $1$ 列、第 $1$ 小块中“$1$”已经被填写过了，继续递归 dfs(2)。进入第 $2$ 层 dfs 函数，$x = 2$。要枚举第 $2$ 个格子的数字，先从 $1$ 开始，发现第一行已经有 $1$ 了，不行；于是尝试填入 $2$，没问题，就记录 $2$，同时记录第 $1$ 行、第 $2$ 列、第 $1$ 小块中“$2$”已经填写过了，继续递归 dfs(3)。进入第 $3$ 层 dfs 函数，$x = 3$。要枚举第 $3$ 个格子的数字。填写 $1$ 和 $2$ 是不行的，但是可以填写 $3$。同时记录下第 $1$ 行、第 $3$ 列、第 $2$ 小块中“$3$”已经填写过了，继续递归 dfs(4)。进入第 $4$ 层 dfs 函数，$x = 4$。要枚举第 $4$ 个格子的数字。这里只能填写 $4$ 了，然后记录下来，继续递归 dfs(5)。进入第 $5$ 层 dfs 函数，$x = 5$。要枚举第 $5$ 个格子的数字。$1$ 不行（第一列重复），$2$ 也不行（第一小块重复），填写 $3$，同时记录第 $2$ 行、第 $1$ 列、第 $1$ 小块“$3$”已经填写过了，继续递归 dfs(6)。……一直到 dfs(16) 填写完最后一个数字 $1$ 后，继续递归 dfs(17)。发现 $x = 17$ 意味着所有格子已经填写完毕，得到了一个合法的解，因此记录答案，然后返回上一层，也就是在 dfs(16) 中继续枚举 $2$、$3$、$4$……如果没有可行解，就再返回上一层 dfs(15)，继续往后枚举。如果在运行到某一层的时候所有选项都不是合法的，那么自然是不能往下面递归的。遇到这种情况，就返回上一层，然后继续枚举。如上图，在 dfs(11) 中所有选项均不合法，就回退到 dfs(10)。原来的 dfs(10) 中 $i = 1$，于是就继续枚举剩余的选项，比如 $i = 2$（不合法），$i = 3$（合法），然后继续前进到 dfs(11)。洛谷 P1219。在 $n \times n$ 的国际象棋棋盘上放置 $n$ 个皇后使得她们互不攻击。皇后的攻击范围时同一行、同一列、在同斜线上的其他棋子。$n \le 13$，求方案数，并输出前 $3$ 种放法。这题是 DFS 的超级经典的例题。我们考虑到每一行只能放一个，且所有行放在第几列都是不相同的，所以可以对 $n$ 进行枚举全排列（这样就能保证皇后不会攻击到同一行、同一列的其他皇后），然后判断是否有两个皇后在统一斜线上。这种方法比较低效，可以考虑使用搜索回溯算法进行优化。假设 $n = 4$，那么求解可以认为是将 $1$、$2$、$3$、$4$ 填入 $4$ 个空中，代表每一行第几列有一个棋子。填空的时候保证填入的棋子不会和之前的棋子冲突。因为分行枚举棋子位数，所以每行不会冲突。在这里使用 $b1$ 数组，记录下 $b1_i$ 说明第 $i$ 列已经被占。那如何记录某一个斜排已经被占呢？可以发现，对于同一个斜行上的所有坐标点 $(x, y)$ 中，$x + y$ 或 $x - y$ 是定值，因此设立 $b2$ 和 $b3$ 数组，$b2_i$ 用来记录 $x + y = i$ 的斜线是否被占用，$b3_i$ 用来记录 $x - y + 15 = i$ 的斜线是否被占用。注意，因为 $x - y$ 可能小于 $0$，普通的数组的下标不能为负数，因此我们加上 $15$ 的偏移量，来保证下标非负。通过这三个数组，就可以判断出打算填写的位置是否被占（竖排、斜排）。如果被占了，就不能填写在这个位置了。例如，$n = 4$ 时，搜索过程如下：由此，我们就可以写出本题的代码了。#include <iostream> using namespace std; const int N = 100; int n, a[N], ans; bool b1[N], b2[N], b3[N]; // 分别记录 y、x + y、x - y + 15 是否被占用 void dfs(int x) { // 第 x 行的皇后放哪儿 if (x > n) { // 如果所有皇后已经放置 ++ans; // 增加结果数量 if (ans <= 3) { // 输出前 3 种答案 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << '\n'; } return; } for (int i = 1; i <= n; ++i) { if (b1[i] || b2[x + i] || b3[x - i + 15]) continue; a[x] = i; // 记录放置位置 b1[i] = true, b2[x + i] = true, b3[x - i + 15] = true; // 标记占位 dfs(x + 1); // 下一层递归 b1[i] = true, b2[x + i] = true, b3[x - i + 15] = true; // 取消标记 } } int main() { cin >> n; dfs(1); // 从第 1 行开始枚举 cout << ans << '\n'; return 0; }由此，我们总结出了两种常见的需要用到 DFS 的场景。遇到了需要枚举序列的时候，搜索回溯会很好⽤。不需要⽣成所有的序列全排列，⽽是⼀个⼀个地填空，保证填空的时候序列是合法的，这样就可以不⽤枚举很多⽆效序列，节约程序运⾏时间。对于一些枚举或者枚举子集的问题，可以使用搜索回溯来解决。但如果需要枚举的元素比较多（超过几十个），即使是搜索回溯也相当慢。我们将在之后会学到的动态规划中讨论这一情况。DFS 在笔者初学时就遇到了相当大的困难，但这又是比赛中十分重要的拿分技巧，因此请务必认真完成此处的练习。
请注意，如无特殊说明，本文默认序列的下标从 $1$ 开始。线性查找查找就是在给定数据中找到目标数据。比如给一个数组，找到其中等于 $x$ 的数，大于 $x$ 的数，小于 $x$ 的数，大于等于 $x$ 并且小于等于 $y$ 的数的数量、位置等，都是查找算法可以解决的问题。最简单的查找算法就是直接用 for 循环扫描一遍数组，看每一个数，找到想要的数，或者统计想要的结果。比如有多少个数等于 $x$ 就可以写成：for (int i = 1; i <= n; ++i) if (a[i] == x) ++cnt;找到第一个 $x$ 的位置就可以写成：int p = -1; for (int i = 1; i <= n; ++i) if (a[i] == x) { p = i; break; }找出符合要求的数这一节我们来通过线性查找统计有多少个大于等于 $l$ 并且小于等于 $r$ 的数。相关的输入输出已经做好了，我们只需要进行统计。用 for 循环看数组的每一位。#include <iostream> using namespace std; int a[1005]; int main() { int n, l, r, cnt = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; if (a[i] >= l && a[i] <= r) ++cnt; } cout << cnt << endl; return 0; }二分查找二分查找（Binary Search）也称折半查找，它是一种效率较高的查找方法。先从一个例子感受下二分这种思想的魅力：小张在心中想了一个在 $[1, 1000]$ 范围内的整数，她考验小李能否在 $10$ 次机会内猜出来。小李每次会猜一个数，并且能够得到小张的三个回复：太小了、太大了，猜中了。那么采用二分的思想，小李第一个猜的数会是 $500$，他会根据小张的回复进行第二次猜数：猜中了，游戏结束。太大了，那么说明范围在 $1 \sim 499$ 以内，于是小李下次猜 $250$。太小了，那么说明范围在 $501 \sim 1000$，于是小李下次猜 $750$。这样小李每次猜不中的时候都会把范围缩小一半，而 $\log_2 1000 < 10$，因此 $10$ 次以内一定能够猜出来。二分查找最常见的一类问题是：在一个有序、无重复元素的数组中找出某个关键字。比如现在有一个包含 $n$ 个元素的递增数组，想要在其中找到元素 $x$。我们会把 $n$ 个元素分成大致相等的两部分，取 $a_{\frac{n}{2}}$ 与 $x$ 做比较。如果 $x = a_{\frac{n}{2}}$，则找到 $x$ 算法中止。如果 $x < a_{\frac{n}{2}}$，则只要在数组 $a$ 的左半部分继续查找 $x$。如果 $x > a_{\frac{n}{2}}$，则只要在数组 $a$ 的右半部分继续查找 $x$。二分查找的算法要求必须采用顺序存储结构（支持随机访问），比如数组，vector（上节学过）。必须按关键字大小有序排列。二分查找的过程下面我们用一个具体例子来说明二分查找算法过程。在这个例子中，我们要从 $1$，$3$，$5$，$7$，$10$，$12$，$14$ 中找出关键字 $12$。首先，用三个值来标记数组的待查找区间的左端点 $left$、右端点 $right$ 和中间位置 $mid$。我们发现，中间位置 $mid$ 指向的值 $7 < 12$，因此，要找的元素一定在 $mid$ 的右边。于是我们将左端点 $left$ 修改为 $mid + 1$，继续后面的查找过程。此时，更新 $mid$，发现 $mid$ 指向的值就是我们要找的 $12$，二分查找结束。这里的 $mid$ 一般取 $\left \lfloor \dfrac{l + r}{2} \right \rfloor$。（有没有更好的表示方法？）如果关键字并没有在数组中出现，整个查找的过程是怎样的呢？我们还是用上面给出的数据 1 3 5 7 10 12 14 作为例子。要在其中查找关键字 $11$，和之前一样，先确定三个标记的位置。接下来，判断待查关键字 $11$ 和 $mid$ 指向的值的关系，发现 $11 > 7$，去右侧继续查询：接下来，判断待查关键字 $11$ 和 $mid$ 指向的值的关系，发现 $11 < 12$，去左侧继续查询：接下来，判断待查关键字 $11$ 和 $mid$ 指向的值的关系，发现 $11 > 10$，去右侧继续查询：此时，由于 $left$ 比 $right$ 更大，说明没有找到关键字 $11$，查询结束。二分查找的步骤$x = a_{mid}$: 找到，结束查找$x < a_{mid}$：在 $[left, mid - 1]$ 中继续査找 $x$。$x > a_{mid}$：在 $[mid + 1, right]$ 中继续査找。如此重复进行，直到查找成功或范围缩小为空 $(left > right)$ 即查找不成功为止。比较次数给定一个数组 $a$ 为 $\{1, 2, 3, 5, 8, 13\}$，其中数组下标从 $0$ 开始，使用二分查找看 $10$ 在不在数组中。刚开始 $left = 0$，$right = 5$，每次取 $mid$ 为 $\left \lfloor \dfrac{left + right}{2} \right \rfloor$，需要看 $3$ 次不同的 $mid$ 才能完成查找。binary_search()在 C++ 中，我们可以很方便地使用 sort() 对一个数组进行排序，而不需要写出很长的排序算法的程序。那么，我们能不能用简单现成的函数来实现对一个数组的二分查找呢？答案是肯定的。在 C++ 中，我们可以用 binary_search() 对一个数组进行二分查找。不过，在使用 binary_search() 之前，我们应该先引入 algorithm 头文件。#include <iostream> #include <algorithm> using namespace std; int main() { int a[] = {1, 2, 3, 4, 5, 7, 9}; cout << binary_search(a, a + 7, 3) << endl; cout << binary_search(a, a + 7, -5) << endl; cout << binary_search(a, a + 7, 5) << endl; cout << binary_search(a, a + 7, 2) << endl; cout << binary_search(a, a + 7, 10) << endl; return 0; }和 sort() 的用法比较类似，binary_search() 一共有三个参数，其中前两个参数表示查找的区间，a 和 a+7 表示从 $a_0$ 到 $a_6$ 进行查找。这点与 sort() 类似， binary_search(a + l, a + r, x) 是在 $a_l$ 到 $a_{r - 1}$ 中进行查找。 binary_search() 的最后一个参数表示要查找的元素值。在进行二分查找前，需要保证待查找的部分是从小到大有序的，一般情况下可以先将整个数组从小到大排序。数组中有重复元素不影响查找。函数的返回值为 bool 类型，当返回 true 时，表示在数组中找到了这个值，否则表示没找到这个值。注意，如果 $a$ 是一个 vector，需要使用 .begin() 和 .end()，即 binary_search(a.begin(), a.end(), x)，或者 binary_search(a.begin() + l, a.begin() + r, x)。使用 binary_search()有 $n$ 个数，$q$ 次询问，每次要查找的数是 $x$。#include <iostream> #include <algorithm> using namespace std; int n, x, q, a[1005]; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; sort(a + 1, a + n + 1); cin >> q; while (q--) { cin >> x; if (binary_search(a + 1, a + n + 1, x)) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }lower_bound() 与 upper_bound()在很多情况下，我们不仅仅要判断一个值是否在有序数组中出现，例如对于如下的数组：1 2 2 3 4 4 4 4 5 6 7 9 9 10我们有如下的两个问题：找出第一个出现的 $4$ 的位置。找出第一个比 $4$ 大的位置。用 binary_search() 是肯定解决不了的，那么，是否有对应的函数来帮我们解决这两个问题呢？在 C++ 里，还有两个非常好用的函数：lower_bound() 和 upper_bound()，它们也在头文件 algorithm 里。其中，lower_bound() 返回第一个大于等于要查找的元素值的位置，upper_bound() 返回第一个大于要查找的元素值的位置。它的参数和 binary_search() 类似，也是三个，首位置，尾位置和要查找的元素，不过返回值是找到的相应元素的位置。lower_bound() 意思是“下界”，在这里是说这个数出现的位置最靠前也就是这个位置了，也就是第一个大于等于这个数的位置。upper_bound() 意思是“上界”，在这里是说这个数出现的位置不能在这个位置及以后了，也就是第一个大于这个数的位置。这两个函数也要求数组是升序的。例如，假设这是一个数组 $a$（下标从 $1$ 开始），那么对于函数 upper_bound(a + 1, a + 15, 4) 和 lower_bound(a + 1, a + 15, 4) 的示意如下：1 2 2 3 4 4 4 4 5 6 7 9 9 10 ^ upper_bound ^ lower_bound因为返回值是位置，所以想要得到数组下标需要减掉数组首位置，所以 upper_bound(a + 1, a + 15, 4) - a 的值为 $9$，也就是会找到上面数组中的第一个 $5$；而 lower_bound(a, a + 14, 4) - a 的值为 $5$，也就是会找到上面数组中的第一个 $4$。如果没有找到，返回的位置为查找区间的尾位置，比如这里就是 a + 15 这个位置。这种情况在实际使用的时候可能需要特判。在 vector 中要相应使用 .begin() 和 .end()，比如 lower_bound(a.begin(), a.end(), x) - a.begin()。如果想要找到最后一个小于查找值的数或者最后一个小于等于查找值的数呢？还是看刚才的例子：1 2 2 3 4 4 4 4 5 6 7 9 9 10 * ^ upper_bound * ^ lower_bound这回想要的是就是两个标了 * 的位置，发现：最后一个小于等于查找值的数的位置就是 upper_bound() 的位置往前一位。最后一个小于查找值的数的位置就是 lower_bound() 的位置往前一位。所以使用 lower_bound() 或者 upper_bound() 以后，算出下标再减 $1$ 就可以了。特别注意如果函数返回的就是首位置，那就说明没有小于或小于等于查找数的元素，需要特判。使用 lower_bound() 和 upper_bound()我们来在数组中找到大于等于 $x$ 的最小的数和大于 $x$ 的最小的数。不过要注意，如果没有找到结果，函数返回的是尾位置，这里会是 a + n + 1，算出来的 $p1$ 的值是 $n + 1$，这个需要特判。如果 $p1 \neq n$ 就输出 $a_{p1}$，否则输出 $\texttt{No}$ 输出以后换行。#include <iostream> #include <algorithm> using namespace std; int n, x, p1, p2, a[1005]; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; sort(a + 1, a + n + 1); cin >> x; p1 = lower_bound(a + 1, a + n + 1, x) - a; p2 = upper_bound(a + 1, a + n + 1, x) - a; if (p1 != n + 1) cout << a[p1] << endl; else cout << "No" << endl; if (p2 != n + 1) cout << a[p2] << endl; else cout << "No" << endl; return 0; }提示有一个从小到大排好的序的下标为 $1$ 到 $n - 1$ 的升序数组 $a$，想要知道其中元素 $x$ 的数量，可以使用 upper_bound(a + 1, a + n + 1, x) - lower_bound(a + 1, a + n + 1, x)。使用 binary_search() 函数时数组待查找部分必须是从小到大排序的。练习小张给出若干个整数，询问是否有一对数的和等于给定的数。输入格式共三行。第一行是整数 $n$（$1 \le n \le 10^5$），表示有 $n$ 个整数。第二行是 $n$ 个整数，保证整数的范围在 $[0, 2 \times 10^8]$ 之间。第三行是一个整数 $m$（$0 \le m \le 2^{30}$），表示需要得到的和。输出格式若存在和为 $m$ 的数对，输出这两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行 $\texttt{No}$。#include <iostream> #include <algorithm> using namespace std; int n, m, num[100005]; bool f; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; cin >> m; sort(num + 1, num + n + 1); for (int i = 1; i <= n; ++i) if (binary_search(num + i + 2, num + n + 1, m - num[i])) { cout << num[i] << ' ' << m - num[i] << endl; f = true; break; } if (!f) cout << "No" << endl; return 0; }事实上，仍然存在比上述代码更优的算法。但此处代码用于练习 binary_search() 的使用，故不做要求。二分答案二分思想不仅可以在有序序列中快速查询元素，还能高效率地解决一些具有单调性判定的问题。事实上， 二分查找的本质，就是在寻找一个满足 $a_{mid} \ge k$ 这一 条件的最小的 $mid$。由于 $a$ 数组的单调性，我们设计出了这一算法。事实上，在一些具有单调性判定的问题中，我们也可以采用类似方法求解。洛谷 P1873。$N$ 棵树高度分别为 $a_1 \cdots a_N$，对于一个砍树高度 $H$， 可以锯下并收集到每棵树上比 $H$ 高的部分的木材。求最大的整数高度 $H$， 使得能够收集到长度为 $M$ 的木材。其中 $N \le 10^6$， 树高不超过 $10^9$。样例输入5 20 4 42 40 26 46样例输出36在样例中，每棵树的高度分别是 $\{4, 42, 40, 26, 46\}$，需要将锯子的高度调整为 $36$，这样可以分别锯下 $\{6, 4, 10\}$ 高度的木材。如果锯子高度再高一点就不能满足要求了。先来变换一下题目：令“条件”表示“当砍树高度为 $x$ 时可以获取不少于 $M$ 的木材”，那么就是要找最大的 $x$ 使得“条件”成立。显然，这一条件是存在单调性的。斧头高度越低，则砍下时，收获的木头越多。即然如此，就可以采用二分的思路来寻找这个数。int find(int l, int r) { // 使用前确保答案在 [l, r] 内 int ans, mid; while (l <= r) { // 闭区间上的二分结束条件 int mid = (l + r) / 2; if (check(mid)) // 条件成立 ans = mid, r = mid - 1; // 这里只需要记录满足条件的 mid，最后循环一定会结束，也一定会在 ans 中保留正确的答案 else l = mid + 1; } return ans; }接下来，我们的问题就改变为如何判断给定的 $x$ 是否能使条件成立（即 check() 函数）。当砍树高度为 $x$ 时，对于某棵树，如果其高度高于 $x$，则砍去高于 $x$ 的部分，否则舍弃，就能统计处砍掉的高度。接着将砍去的高度求和，再与 $M$ 相比即可。bool check(int h) { // 当砍树高度为 h 时能否得到大于 m 的木材 long long tot = 0; for (int i = 1; i <= n; ++i) if (a[i] > h) tot += a[i] - h; // 按照题意模拟 return tot >= m; }需要注意的是，这里的 $r$ 的初始值应当大于等于所有树中最高者的高度，否则可能无法通过二分的到正确的结果。判断条件是否成立的算法复杂度是 $O(n)$，而二分答案本身的算法度复杂度是 $O(\log A)$ ，其中 $A$ 是指最高的高度，因此总复杂度是 $O(n \log A)$。通过本题 ，我们可以得到使用二分答案的条件：命题可以被归纳为找到使得某命题 check(x) 成立（或不成立）的最大（或最小）的 $x$。把 check(x) 看做一个值为真或假的函数，那么它一定在某个分界线的一侧全为真，另一侧全为假。可以找到一个复杂度优秀的算法来检验 check(x) 的真假。通俗来讲，二分答案可以用来处理形如“最大值最小”或“最小值最大”的问题。
请注意，如无特殊说明，本文默认序列的下标从 $1$ 开始。我们先来看一个简单的例子：你现在有面值为 $20$ 元、$10$ 元、$5$ 元、$1$ 元的纸币足够张，现在想用最少张数的纸币支付 $58$ 元。最差的方法是支付 $58$ 张 $1$ 元的纸币，但我相信你肯定不会这么做。你会按下面的步骤想：$20$ 元纸币用 $2$ 张，还需凑 $18$ 元。$10$ 元纸币用 $1$ 张，还需凑 $8$ 元。$5$ 元纸币用 $1$ 张，还需凑 $3$ 元。$1$ 元纸币用 $3$ 张，刚好凑出了 $58$ 元，一共用了 $7$ 张纸币。即优先用大面值的纸币，能用多少就用多少，然后再一步步考虑小面值，这其实就是一种贪心的思想。像这种贪心是显而易见的，也不难证明其正确性，而有些贪心结论却隐藏得很深。求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。这类问题我们可以采用贪心思想来解决，我们在每一步都做出当前看起来最正确的决定，这些决定组合起来，就可以得到整个问题的最优解，即通过做出局部最优选择来构造全局最优解。还有一种算法叫做动态规划（Dynamic Programming, DP），常用于处理那些不适用贪心的最优化问题，我们将在之后学习这部分内容。下面，我们通过几个例子，由浅入深地带领大家学习贪心算法。马上又到了一年一度的新年联欢，小明作为班里的班长，负责组织策划新年联欢活动，他决定采购一些奖品奖励积极参与每个项目活动的同学。为了激励更多的人参与活动，需要采购的奖品数目越多越好。班费中可支出的钱数为 m元，现给定商店中几种可作为奖品的物品的价格和库存数量，怎样才能购得最多的物品数？输入格式输入共 $n + 1$ 行：第一行包含两个正整数 $m$（$1 < m < 10^4$）和 $n$（$1 < n < 100$），表示可支出的费用为 $m$ 元和可供购买的物品有 $n$ 种。接下来 $n$ 行，每行包含两个数（以空格分隔），分别表示一种物品的单价 $a_i$ 和库存数量 $b_i$。保证 $a_i, b_i \le 1000$。输出格式输出一行一个整数，表示最多可以购买的物品数量。样例输入500 6 100 3 20 15 50 10 35 5 5 6 60 2样例输出25样例解释价格为 $5$ 的可以买 $6$ 个，价格为 $20$ 的可以买 $15$ 个，价格为 $35$ 的可以买 $4$ 个，总共 $25$ 个奖品。本题的贪心结论很简单：我们只需按单价从小到大排序，每次尽可能地买单价低的物品。因为每购买一件物品，我们都希望剩余的钱更多。从这里可以看出，贪心就是人的一种本质思想，在现实中你也会优先选择更便宜的。本题的核心代码如下：const int N = 110; struct node { int x, y; // x 表示价格，y 表示个数 } a[N]; bool cmp(node p1, node p2) { // 结构体排序函数 return p1.x < p2.x; } sort(a + 1, a + n + 1, cmp); int ans = 0; for (int i = 1; i <= n; ++i) { int t = min(m / a[i].x, a[i].y); // 剩余的钱最多可以买多少个 a[i] m -= a[i].x * t; ans += t; }哈利波特在与伏地魔的战斗中毁坏了自己的魔杖，于是他决定去奥利凡德的魔杖店买个新的。他在店里看到几个魔杖和几个盒子，每个魔杖的长度为 $X_1, X_2, \cdots, X_n$，每个盒子的长度为 $Y_1, Y_2, \cdots, Y_n$。一个长度为 $X$ 的魔杖能放进长度为 $Y$ 的盒子里，当且仅当 $X \le Y$。哈利想知道他能否把所有魔杖都放进盒子里，并且每个盒子只能放一根魔杖。请你帮他解决这个问题。输入格式第一行一个整数 $n$（$1 \le n < 100$），表示魔杖的数量。第二行 $n$ 个整数 $X_i$（$1 \le X_i < 10^9$），表示每根魔杖的长度。第三行 $n$ 个整数 $Y_i$（$1 \le Y_i < 10^9$），表示每个盒子的长度。输出格式如果哈利能把所有魔杖放进盒子里，输出 $\texttt{DA}$，否则输出 $\texttt{NE}$。样例输入3 7 9 5 6 13 10样例输出DA先尝试把最长的魔杖的放进最长的盒子里，然后尝试把第二长的魔杖放进第二长的盒子里……最后尝试把最短的魔杖放进最短的盒子里。显然这样就一定是最优配对了，如果这种方法都无法实现，更别说其他的放法了。参考代码：sort(a + 1, a + n + 1); // 给盒子排序 sort(b + 1, b + n + 1); // 给魔杖排序 bool ok = true; for (int i = 1; i <= n; ++i) if (a[i] > b[i]) { ok = false; break; } if (ok) cout << "DA" << endl; else cout << "NE" << endl;洛谷 P1223。有 $n$（$1 \le n \le 1000$）个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这几个人排队的一种顺序，使得几个人的平均等待时间最小。输入格式第一行为一个整数 $n$。第二行 $n$ 个整数，第 $i$ 个表示第 $i$ 个人的节水时间 $T_i$。输出格式输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。样例输入10 56 12 1 99 1000 234 33 55 99 812样例输出3 2 7 8 1 4 9 6 10 5 291.90我们的贪心策略是：让接水时间少的人先接水。参考代码：#include <iostream> #include <algorithm> #include <iomanip> using namespace std; const int N = 1010; int n; double sum; struct water { int num, time; } p[N]; bool cmp(water a, water b) { if (a.time != b.time) return a.time < b.time; return a.num < b.num; } int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> p[i].time; p[i].num = i; } sort(p + 1, p + n + 1, cmp); for (int i = 1; i <= n; ++i) { cout << p[i].num << ' '; sum += i * p[n - i].time; } cout << endl; cout << fixed << setprecision(2) << sum / n << endl; // 输出保留两位小数 return 0; }Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。所有 $N$（$1< N < 20,000$）头奶牛都有一个确定的身高 $H_i$（$1 < H_i < 10,000$）。设所有奶牛身高的和为 $S$，书架的高度为 $B$，并且保证 $1 \le B \le S < 2,000,000,007$。为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。输入格式从文件 shelf.in 读入。第 $1$ 行有两个用空格隔开的整数 $N$ 和 $B$。第 $2$ 到第 $N + 1$ 行，每行有一个整数，表示 $H_i$。输出格式输出到文件 shelf.out。输出一行一个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部。样例输入6 40 6 18 11 13 19 11样例输出3样例解释一共有 $6$ 头奶牛，书架的高度为 $40$，奶牛们的身高在 $[6, 19]$ 之间。一种只用 $3$ 头奶牛就达到高度 $40$ 的方法为 $18 + 11 + 13$。当然还有其他方法，此处省略。贪心策略是什么？显然地，为了保证奶牛数量尽可能少，我们需要选择尽可能高的奶牛。本题中出现了“从文件读入”和“输出到文件”的字样，这意味着我们不能再像之前一样在控制台里操作了（就是运行之后弹出的黑色窗口），而是在文件中完成输入和输出操作。我们可以将文件 shelf.in 和 shelf.out 放到源代码文件的同一目录下，然后在主函数开头加入以下语句来实现对样例文件的输入与输出：freopen("shelf.in", "r", stdin); freopen("shelf.out", "w", stdout);其中，shelf.in 与 shelf.out 为文件名。上述代码表示从 shelf.in 文件中读取数据，并将结果输出到 shelf.out 文件中。如果目录下没有 shelf.out 文件，那么程序会自动创建它，并且将输出写入其中。但提交时，仍然仅需要提交这份代码，不需要提交输入输出文件。通常情况下，比赛中会为你提供几组大样例，样例文件中包含后缀名为 .in 的输入文件与 .ans 的答案文件。你可以将输出的 .out 文件与后缀名为 .ans 的样例文件比较，以达到调试程序的目的。我们将参加的 CSP-J/S 和后续的 NOIP 比赛中也将使用这样的输入输出方式，所以请确保完全理解这部分内容。参考代码如下：#include <iostream> #include <algorithm> using namespace std; const int N = 20010; int n, m, a[N]; int main() { freopen("shelf.in", "r", stdin); freopen("shelf.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; sort(a + 1, a + n + 1); for (int i = n; i; --i) { m -= a[i]; if (m <= 0) { cout << n - i + 1 << endl; break; } } return 0; }番茄君在奶茶店打工，他把几个杯子排成一行，然后随意地往里面加上珍珠，已知第 $i$ 个杯子的珍珠数目是 $a_i$。突然他想起来老板让他少用珍珠，必须满足相邻两个杯子里的珍珠数目不超过 $m$。现在他只能把多余的珍珠去掉，放回冰箱里（没错，就是这么不卫生）。请你帮他计算下，最少需要去掉多少珍珠。输入格式从文件 tea.in 读入。第一行两个整数 $n, m$（$2 \le n \le 10^5, 1 \le m \le 10^9$）。第二行 $n$ 个整数，表示初始时每个杯子里的珍珠数目 $a_i$（$1 \le a_i \le 10^9$）。输出格式输出到文件 tea.out。输出一个整数，表示最少需要去掉的珍珠数目。样例 #1 输入3 10 7 8 10样例 #1 输入8样例 #2 输入3 10 15 1 10样例 #2 输出6参考代码如下：#include <iostream> using namespace std; const int N = 1e5 + 10; // 1e5 表示 1 乘 10 的 5 次方 int n, m, a[N]; long long ans; int main() { freopen("tea.in", "r", stdin); freopen("tea.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 2; i <= n; ++i) if (a[i] + a[i - 1] > m) { ans += a[i] + a[i - 1] - m; a[i] = max(0, m - a[i - 1]); } cout << ans << endl; return 0; }在某次膜拜大会上，一些神牛被要求集体膜拜。这些神牛被奖励每人吃一些神牛果。但是，每个神牛的肚量不一样。为了不显得某些人吃得太多，决定两人一组，使得吃得最多的那组吃得尽量少。输入格式第一行一个偶数 $n$（$n \le 10^4$）。第二行有 $n$ 个正整数，为给定的一列数字，表示每个神牛能吃多少神牛果。数字均小于 $10^9$。输出格式输出一个正整数，表示吃的最多的一组神牛吃的个数的最小值。样例输入4 1 5 2 8样例输出9遇事不决先排序，我们首先会把所有整数从小到大排序，排序后的结果为 $a_1, a_2, \cdots, a_n$。当 $n=2$ 时，只有一种分配方案，答案为 $a_1 + a_2$。当 $n = 4$ 时，有 $3$ 种分配方案：$a_1 + a_2$ 和 $a_3 + a_4$，显然后者更大。$a_1 + a_3$ 和 $a_2 + a_4$，显然后者更大。$a_1 + a_4$ 和 $a_2 + a_3$。容易发现，前两种方案都比较浪费，可以通过适当的调整更优。而第三种方案，无论 $a_1 + a_4$ 还是 $a_2 + a_3$ 更大，都比前两种方案小。那么就能想到贪心策略是每次用最小的和最大的来配对，即 $(a_1, a_n), (a_2, a_{n - 1}), \cdots, (a_{\tfrac{n}{2}}, a_{\tfrac{n}{2}} + 1)$，然后答案就为其中的最大值。洛谷 P1803。在坐标轴上有几条线段，每条线段的左端点为 $x_i$，右端点为 $y_i$。现在你需要删去部分线段，使得剩下的线段除端点外无公共部分。请你计算最多能保留的线段数目。输入格式第一行一个整数 $n$（$1 \le n \le 10^6$），表示线段的条数。接下来 $n$ 行，每行两个整数 $x_i, y_i$（$0 \le x_i < y_i \le 10^6$）。输出格式一个整数，表示最多能保留的线段数。样例输入6 6 8 3 6 4 7 1 4 7 9 0 5样例输出3首先我们会想到一种贪心策略：优先选择长度较短的区间。容易举出反例：如果刚开始选了绿色线段就没法选其他线段了，而更优的方法是选择红色线段。所以这种贪心策略是错误的。我们又想到第二种贪心策略：把左端点从小到大排序，从左到右一条条覆盖，记录一下当前已经覆盖到的最右边位置，然后每次插入左端点大于该位置且左端点最小的线段。依然能举出反例：红色线段的左端点最小，但是实在太长了，选了它就没法选别的线段了，不如选两条绿色线段。所以这种贪心策略也是错误的。那么我们就想到第三种贪心策略：把右端点从小到大排序，从左到右一条条覆盖，记录一下当前已经覆盖到的最右边位置,然后每次插入左端点大于该位置且右端点最小的线段。这种贪心策略是正确的，因为我们的目的就是让所选的线段尽可能早的结束，这样能给予更多的空间来选择剩余的线段。如上图所示，我们会选择三条绿色线段。参考代码如下：#include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int n, ans, now; // now 用于记录右端位置 struct node { int x, y; } a[N]; bool cmp(node p1, node p2) { return p1.y < p2.y; } int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y; sort(a + 1, a + n + 1, cmp); for (int pos = 1; pos <= n; ++pos) if (a[pos].x >= now) { now = a[pos].y; ++ans; } cout << ans << endl; return 0; }同一个问题，可能有多种贪心策略。贪心选择性质是：全局最优解可以通过局部最优选择来达到。有 $N$ 组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界 $R$ 和下界 $L$（$L \le R$），每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以让 $N$ 组学生的人数都在 $[L, R]$ 中。输入格式第一行一个整数 $N$（$1 \le N \le 50$），表示学生组数。第二行 $N$ 个整数，表示每组的学生个数 $a_i$。第三行两个整数 $L, R$，表示下界和上界。保证 $1 \le a_i, L, R \le 1000$。输出格式一个整数，表示最少的交换次数，如果不能满足题目条件输出 $-1$。样例输入3 1 5 10 4 7样例输出3参考代码如下：#include <iostream> using namespace std; const int N = 60; int n, a[N], l, r, sum, ans1, ans2; int main() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i]; cin >> l >> r; if (sum >= l * n && sum <= r * n) { for (int i = 1; i <= n; ++i) { // 人数越多的越往少的里面加 if (a[i] < l) ans1 += l - a[i]; // 少的补人 if (a[i] > r) ans2 += a[i] - r; } cout << max(ans1, ans2) << endl; } else cout << -1 << endl; return 0; }由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。注：每天所有奶农的总产量大于 Marry 乳业的需求量，输入格式第一行两个整数 $N$（$1 \le N < 2, 000, 000$）和 $M$（$1 \le M < 5, 000$）是提供牛奶的农民个数。接下来 $M$ 行，每行两个整数 $p_i$（$0 \le p_i \le 1000$）和 $x_i$（$1 \le x_i \le 100$），分别表示农民 $i$ 的牛奶的单价与产量。输出格式单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。参考代码如下：#include <iostream> #include <algorithm> using namespace std; const int N = 5010; int n, m, ans; struct node { int p, x; } a[N]; bool cmp(node p1, node p2) { return p1.p < p2.p; } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i].p >> a[i].x; sort(a + 1, a + m + 1, cmp); for (int i = 1; i <= m; ++i) { int t = min(a[i].x, n); ans += t * a[i].p; n -= t; if (n == 0) break; } cout << ans << endl; return 0; }
有些目标是宏大的，比如要在 IOI 赛场中得到满分（俗称AK IOI）。如果现在还是一个普通的学生，那么想达成这个目标太难了。但把这样宏大的目标分解为很多个子任务，就不会感觉那么复杂了。要想 AK IOI，首先需要入选国家队，参加 IOI。那怎么成为入选国家队呢？参加中国队选拔赛并通过面试答辩即可。使用同样的思路往前倒推，直到最后只剩下最基础的任务（比如认真的读完这章内容并完成练习），做完这样的小任务就很简单了。如何 AK IOI，如图 1 所示。图 1 - 如何 AK IOI像这样将一个很大的任务分解成规模小一些的子任务，子任务分成更小的子任务，直到遇到初始条件，最后整理归纳解决大任务的思想就是递推与递归思想，不过这两者还是有一些区别。本文涉及的内容是动态规划思想与分治策略的基础，也请各位认真学习，说不定目标就真的达到了。递推思想学校楼梯有 $N$（$N \le 50$）阶，上楼可以一步上一阶，也可以一步上二阶，计算共有多少种不同的走法。例如：$N = 4$ 时有以下 $5$ 种走法：$0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$。$0 \rightarrow 1 \rightarrow 2 \rightarrow 4$。$0 \rightarrow 1 \rightarrow 3 \rightarrow 4$。$0 \rightarrow 2 \rightarrow 3 \rightarrow 4$。$0 \rightarrow 2 \rightarrow 4$。假设想求 $1000$ 个台阶的走法数量，这看起来是个非常宏伟的目标！最简单暴力的思路就是使用回溯法来枚举所有走法，但是速度非常慢，如果数据范围稍大就会超时。如果想要走到第 $1000$ 个台阶时，必须要先走到第 $998$ 个台阶或者 $999$ 个台阶，然后一步跨到第 $1000$ 级，所以到第 $1000$ 个台阶的走法数量就是从头到第 $998$ 级的走法数量与从头到第 $999$ 级的走法数量之和，这么想就简单多了。不过还得先知道走到第 $998$ 级和 $999$ 级的走法数量是多少。假设从头走到第 $i$ 个台阶的走法数量是 $f_i$，根据上面的分析可以得到 $f_{1000} = f_{998} + f_{999}$。同理，$f_{999} = f_{997} + f_{998}$……以此类推，可以归纳得到：$$ f_i = f_{i - 2} + f_{i - 1} $$最后一步的走法如图 2 所示。图 2 - 最后一步的走法有些读者看到这个可能会感觉有些眼熟。在语言入门的循环一章有介绍过这样的内容：后一项等于前面两项之和，这就是斐波那契数列。即使归纳得到了这个式子（称为递推式），也还不能说明这是一个斐波那契数列。因为根据这个递推式往前追溯，总得有个尽头（称为初始条件）。观察一个数列 $\{1, 3, 4, 7, 11, 18, 29, 47 \cdots \}$，虽然从第三项开始每一项都符合这个递推式，但是这个数列的初始条件和斐波那契数列不一样，所以这个数列和斐波那契数列相差甚远了。计算数列中的某个元素只需要得到它前面的两项元素即可。如果知道 $f_1$ 和 $f_2$ 的值，就可以推导出 $f_3 = f_1 + f_2$，继而得到 $f_4 = f_3 + f_2$，……一直可以计算得到 $f_{1000} = f_{998} + f_{999}$。获得 $f_1$ 和 $f_2$ 的值，作为初始条件就至关重要。那么，对于这个问题而言初始条件是什么呢？可以直接进行分析。当只有一个台阶时，跨一步就可以上去了，这是唯一的一种走法：而有两个台阶时，可以走两次一步，或者走一次两步，一共两种走法。所以可以确定 $f_1 = 1$，$f_2 = 2$。现在有了递推式，有了初始条件，就可以获得完整的数列了。经过计算,可以得到这个数列前面几项是 $\{ 1, 2, 3, 5, 8, 13, 21 \cdots \}$，这就是斐波那契数列从第 $2$ 项开始的序列。请注意斐波那契的初始条件是 $f_1 = f_2 = 1$。像这样知道递推式，也知道初始条件，从初始条件开始往上顺推直到求得目标解的思想就是递推。本题的核心代码如下：int n, f[5010]; int main() { cin >> n; f[1] = 1, f[2] = 2; for (int i = 3; i <= n; ++i) f[i] = f[i - 2] + f[i - 1]; cout << f[n] << endl; return 0; }许多问题也可以套用斐波那契数列，比如假定每对大兔每月能生产一对小兔，而每对小兔生长为大兔也需要一个月，已知现在有 $1$ 对小兔，请问 $N$ 个月后一共有几对兔子。请进行归纳证明。当就某个问题能写出递推式、能确定初始（边界）条件，那么可以考虑使用递推。对于某些数据规模很大的递推任务可以使用矩阵加速提升效率，由于难度较大，此处不作讲解。洛谷 P1002。棋盘左上角 $(0, 0)$ 有一个过河卒，需要走到右下角 $(n, m)$，卒每次可以向下或者向右一格。棋盘上有一个固定的对手的马，该马所在的点和所有跳跃一步可达的点（马走日）称为对方马的控制点，卒无法经过。求卒从起点到终点所有的路径条数。如图 3， 当卒要从 $(0, 0)$ 往右或下走到 $(6, 6)$，马在 $(3, 3)$。马能跳到的位置已经打上了叉，卒不能走到这些点，一共有 $6$ 种合法方案。图 3 - 马拦过河卒中的一个例子暴力枚举还是枚举往右或往下然后回溯搜索，依然会超时。如果那个马不存在，从左上角到右下角一共有多少种走法？记从原点 $(0, 0)$ 走到坐标 $(i, j)$ 的方法数量是 $f_{i, j}$ 。定义一个二维数组 $f$，记录从原点 $(0, 0)$ 走到坐标 $(i, j)$ 的方法数量是 $f_{i, j}$。当卒从起点开始，笔直往右或者笔直往下，无论走多远都只有唯一的一种走法（因为一旦偏移就再也回不去了），所以当 $k \ge 0$ 时，$f_{k, 0} = f_{0, k} = 1$。这就是初始条件。如何到点 $(1, 1)$ 呢？要么是从点 $(0, 1)$ 走下一格，要么是从点 $(1, 0)$ 往右走一格，因此到 $(1,1)$ 的方案数量就是到 $(0, 1)$ 的数量加上到 $(1, 0)$ 的数量，即 $f_{1, 1} = f_{0, 1} + f_{1, 0}$。可以归纳得到当 $i > 0$ 且 $j > 0$ 时，有：$$ f_{i, j} = f_{i - 1, j} + f_{i, j - 1} $$这就是递推式。有了递推式，有了初始条件，就可以求出完整的 $f$ 数组的值了，如果没有碍事的马，$f$ 数组如图 4 所示：图 4 - 二维数组递推如果有些点因为马的把守而不能走呢？其实也没有什么区别，只不过没办法从马的控制点转移到下一个点罢了（换句话说，马的控制点上路径数全部清空）。此外，初始条件和递推范围也有一点变化，只需要 $f_{0, 0} = 1$ 即可，同时递推范围就是 $i \ge 0, j \ge 0, j \neq 0$（想一想，为什么）。代码如下：#include <iostream> using namespace std; const int N = 25; // 马的控制范围相对于马的位置的偏移量 const int d[][] = {{0, 0}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; int n, m, hx, hy; bool ctrl[N][N]; long long f[N][N]; int main() { cin >> n >> m >> hx >> hy; for (int i = 0; i < 9; ++i) { int tmpx = hx + d[i][0], tmpy = hy + d[i][1]; if (tmpx >= 0 && tmpx <= n && tmpy >= 0 && tmpy >= m) // 判断在棋盘范围内 ctrl[tmpx][tmpy] = true; // 记录马的控制点 } // 若原点就是马的控制点，则初始路径数量就是 0，否则是 1 f[0][0] = 1 - ctrl[0][0]; for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) { if (ctrl[i][j]) continue; // 若这个点是控制点，则跳过 if (i) f[i][j] += f[i - 1][j]; // 若不在横轴上就加上面路径数 if (j) f[i][j] += f[i][j - 1]; // 该点不在纵轴上就加上左边的路径数 } cout << f[n][m] << endl; // 输出答案 return 0; }在实现时，需要预处理哪些点是马的控制点，然后对所有的点进行递推操作。只有转移来的格点存在， 才能累加方案数。洛谷 P1044。有一个单端封闭的管子，将 $n$（$1 \le n \le 18$）个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问倒出来方法总数有多少种？例如，将小球 $[1, 2, 3]$ 依次加入到管子中，倒出来的方法可以是 $[1, 2, 3]$（每倒入一个球后立刻拿出来）$[3, 2, 1]$（倒入全部球然后依次取出）$[2, 3, 1] \ [2, 1, 3] \ [1, 3, 2]$。需要注意的是，$[3, 1, 2]$ 不行，因为加入 $3$ 之前，管子里面已有 $1$ 和 $2$ 了，如果 $3$ 最先出去，那么接下来出去的只能是 $2$，而 $1$ 被压在最底下。设 $i$ 个元素一共有 $f_i$ 种出管方式，求 $n$ 个元素的出管方式。其中每个元素都可能最后一个出管。假设第 $i$ 个小球最后出管：比 $i$ 早入且早出有 $i - 1$ 个数，有 $f_{i - 1}$ 种出管方式。比 $i$ 晚入且早出有 $n - i$ 个数，有 $f_{n - i}$ 种出管方式。一共有 $f_{i - 1} \times f_{n - i}$ 种出管方式。当 $i$ 取值不同的时候，产生的出管序列也是独立的，所以可以加起来。$i$ 的取值范围可以是从 $1$ 到 $n$。所以有递推式：$$ f_n = \sum \limits_{i = 1}^{n} f_{i - 1} \times f_{n - i} = f_0 \times f_{n - 1} + f_1 \times f_{n - 2} + \cdots + f_{n - 1} \times f_0 $$初始条件是 $f_0 = f_1 = 1$。第 $k$ 个小球的出管方式如图 5 所示：图 5 - 第 k 个小球的出管方式代码非常短小：#include <iostream> using namespace std; int n, f[20] = {1, 1}; int main() { cin >> n; for (int i = 2; i <= n; ++i) // 第 i 个元素最后出来 for (int j = 0; j < i; ++j) // i 个元素每个最后出来的方案数相加 f[i] += f[j] * f[i - j - 1]; cout << f[n] << endl; return 0; }像这种只有一个开口、元素先进后出的管子称为栈，我们之后学习线性表时会更详细地学习其使用方式。$f$ 数组里面的数字就是卡特兰数（Catalan Number），前几项是 $1, 1, 2, 5, 14, 42$。卡特兰数有很多奇妙的性质，之后学习到组合数学时会仔细讨论。递归思想之前已经在语言部分介绍过了递归，在排序部分也介绍了快速排序，它们都使用到了递归。这一节不会详细介绍语言层面的递归程序执行机理，而是希望读者能够进一步理解递归思想。算了，还是讲讲吧。递归是函数“自己调用自己”，正确且合理的递归函数在定义上有如下要求：必须有参数。参数必须是按照某种顺序（从小到大或从大到小）变化的。函数体中必须有函数终止条件语句。以求 $n$ 的阶乘为例：long long fact(int n) { if (n == 0 || n == 1) return 1; return n * fact(n - 1); }其递归原理是：递推 + 终止条件 + 回归。如图 6 所示：图 6 - 递归原理解析洛谷 P1028。给出自然数 $n$（$n \le 1000$），最开始时数列中唯一的一项就是 $n$，可以对这个数列进行操作，生成新的数列。请问最后能生成几种不同的数列？原数列直接作为一种合法的数列 ；在原数列的末端加入一个自然数，但是它不能超过该数列最后一个数字的一半；加入自然数后的数列继续按此规则从第一条进行处理，直到不能再增加新元素为止。比如说，输入数字 $6$，这样符合性质的数列有 $\{ 6 \}$、$\{ 6, 1 \}$、$\{ 6, 2 \}$、$\{ 6, 2, 1 \}$、$\{ 6, 3 \}$、$\{ 6, 3, 1 \}$。对于一个整数 $n$，如果只考虑前面两点，那么问题就简单了——答案就是 $\dfrac{n}{2} + 1$。但是这还没完，题目要求新的数列还要按照同样的规则进行处理，该怎么办呢？例如数列最开始只有一个元素 $8$，在末尾加入一个新元素，列表就变成 $\{8, 4\}$、$\{8, 3\}$、$\{8, 2\}$、$\{8, 1\}$，算上 $\{8\}$ 一共有 $5$ 种情况。计算更长的数列的方案数怎么办呢？其实也很好算，分别计算 $n = 4, 3, 2, 1$ 按照这样的操作能有几种情况，然后累加统计即可。以 $4$ 开头（$3, 2, 1$ 同理）的所有合法数列，都可以接续到 $8$ 的后面。如图7。图 7 - 问题规模的分解原来是要解决 $n = 8$ 的问题，现在分解成了四个规模更小但是本质上是同样的子问题。直到 $n = 1$ 时，没法继续分解，可以直接返回唯一一种数列，即 $\{1\}$。然后返回上一层（$n = 2$） 接收到所有小规模问题的答案，合并统计处理获得这个规模下的答案，再返回上一层……直到求得问题的解。像这样构造函数，这个函数在运行过程中调用自己，从而解决问题的思路被称为递归思想。于是可以写出这样的函数：int sol(int x) { if (x == 1) return 1; int ans = 1; for (int i = 1; i <= x / 2; ++i) ans += sol(i); return ans; }其中 sol(x) 是询问规模为 $x$ 时的答案。这样实现函数并没有什么错误，但是并不能通过本题：运行效率很低导致程序超时。这是因为做了很多无效功，比如说 sol(2) 可能由 sol(4) 调用，也有可能被 sol(8) 调用，但是 sol(2) 本身的值是固定不变的，在这里却被重复运行了很多次造成了浪费。为了防止这种情况，可以定义一个数组 $f$，其每一项 $f_i$ 就是当问题规模为 $i$ 的时候的答案。首先将数组初始化为 $-1$，说明 $f_i$ 还没有被计算过。依然使用同样的方法去求解，只是如果发现已经计算过就直接返回 $f_i$ 而不必进行接下来的计算了，否则还是按照刚才递归的方式计算，然后将结果存入数组中以便之后再次调用。改进后的代码如下：#include <iostream> #include <cstring> using namespace std; int n, f[1010]; int sol(int x) { if (f[x] != -1) return f[x]; // 如果分解之后的数已经被记忆过，直接返回值 int ans = 1; // 每个数都能单独构成一个序列 for (int i = 1; i <= x / 2; ++i) ans += sol(i); // 否则把被分解的每个数能构成的序列数相加 return f[x] = ans; // 求和之后存储到被处理的数对应的数组中，记忆化 } int main() { cin >> n; memset(f, -1, sizeof(f)); // 预处理，将数组全部初始化为 -1 f[1] = 1; // 当 n 拆到 1 时，只能生成一种数列 cout << sol(n) << endl; return 0; }这样的话每个数字最多只会计算一次， 因为一旦计算完成就会被存下来，便于日后使用。这样的思想被称为记忆化。事实上，本题也可写出递推式 $f_i = 1 + f_1 + f_2 + \cdots + f_{\tfrac{i}{2}}$，$f_1 = 1$。 请尝试使用递推求解本题。有的情况下进行递推，需要求出初始条件，还需要确定递推顺序，所以这时使用递归思想会容易一些。洛谷 P1464。对于一个递归函数 $w(a, b, c)$，有：$a \le 0$ 或 $b \le 0$ 或 $c \le 0$ 返回 $1$。$a > 20$ 或 $b > 20$ 或 $c > 20$ 返回 $w(20, 20, 20)$。$a < b$ 并且 $b < c$，返回 $w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)$。其他情况返回 $w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)$。输入会有若干行，并以 $\texttt{-1, -1, -1}$ 结束。输出会有若干行，每一行格式形如 $\texttt{w(a, b, c) = ans}$。注意空格。如果输入数据不在 $(0,20]$ 这个范围内，强制返回 $1$ 或者 $w(20, 20, 20)$。根据题意写函数，建立数组记录 $w$ 的值进行记忆化即可。具体代码如下：#include <iostream> using namespace std; long long a, b, c, f[50][50][50]; long long w(long long a, long long b, long long c) { if (a <= 0 || b <= 0 || c <= 0) return 1; if (a > 20 || b > 20 || c > 20) return w(20, 20, 20); if (f[a][b][c]) return f[a][b][c]; if (a < b && b < c) f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c); else f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1); return f[a][b][c]; } int main() { while (cin >> a >> b >> c) { if (a == -1 && b == -1 && c == -1) break; cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl; } return 0; }本题也可以使用递推方法，只是边界问题和枚举顺序稍不好处理， 感兴趣的读者可以自己尝试使用递推实现本题。洛谷 P1928。有一种压缩字符串的方式：对于连续的 $D$（$2 \le D \le 99$）个相同的子串 $X$ 会压缩为“$[DX]$”的形式，而 $X$ 可能可以进行进一步的压缩。比如说字符串 $\texttt{CBCBCBCB}$ 可以压缩为 $\texttt{[4CB]}$ 或者 $\texttt{[2[2CB]]}$ 。现给出压缩后的字符串，求压缩前的字符串原文。假设只有一层方括号，那只需要找到方括号，就可以将该部分还原。如果方括号的“重复部分”里还有方括号呢？没关系，设法把里面的方括号继续展开即可。 因此可以写成递归函数。字符串 $\texttt{ABF[4RA[2A]B[3C]]}$ 的展开如图 8：图 8 - 密码的递归顺序参考代码如下：#include <iostream> #include <string> using namespace std; string expand() { // 展开压缩字符串 string s = "", x; // s 代表被展平字符串，x 代表被压缩的字符串 char c; // 输入字符暂时存放处 int d; // 被压缩字符串的个数 while (cin >> c) { // 不停输入字符，直到输入结束 if (c == '[') { // 如果发现一个压缩区 cin >> d; // 输入被压缩次数 x = expand(); // 被压缩的字符串递归调用展开函数处理 while (d--) s += x; // 按照被压缩次数把被压缩字符串填进 s 里 } else if (c == ']') return s; // 如果碰到右括号，说明压缩区处理完毕 else s += c; // 如果不是压缩区的内容，直接添加进 s 里 } } int main() { cout << expand(); return 0; }小结递推需要确定递推式 、初始（边界）条件，从微观到宏观。递归将一个大的任务分解成若干个规模较小的任务，而且这些任务的形式与结构和原问题一致，然后将结果合并，直到达到边界。有些问题使用递推策略和递归策略都能解决，但有些问题只能将 大问题分割成小问题，但是却很难建立递推式，或者不好确定递 推顺序，这种情况下应当使用递归策略。但递归需要记录每一层的状态， 因此可能会比较占用空间。书本和讲义上的题是完全不够的，请各位学完对应章节后自觉打满某谷进度条。
算法的世界高深莫测，但是很多问题的解决方法简单而粗暴枚举出所有可能的情况，然后判断或者统计，从而解决问题。在很多程序设计比赛中，有许多比较简单的题目是可以通过枚举暴力解决的；而有的更具有挑战性的题目虽然有更巧妙的解法，但依然可以使用枚举，暴力地完成部分任务。本文将介绍一些枚举与暴力策略，这是非常基础而且重要的，但是对初学者来说还是会有一些挑战。请务必理解本章之前的所有知识后再开始本章的学习。枚举就是根据提出的问题，一一列出该问题的所有可能的解，并在逐一列出的过程中，检验每个可能解是否是问题的真正解，如果是就采纳这个解，如果不是就继续判断下一个。枚举法一般比较直观，容易理解，但由于要检查所有的可能解，因此运行效率较低。能够用枚举法解决的题目往往是最简单的一类题目。这种题目具有以下特点：枚举范围是有穷的。检验条件是确定的。验证复杂的程序的正确性，可写功能一致的暴力对照程序，并构造小规模输入数据，比较二者输出。这一过程称作对拍，在赛场上是非常实用的查错技巧。算法问题的分类一般而言，算法问题可以分为两类。模拟问题构造具体描述，使用计算机还原现实规则。每一步的行为大多是简单而确定的，只需按照既定指示行动。常基于数据结构，优化单步操作的复杂度。求解问题在全部的可能性中，搜索可行或最优解。解是不确定的，需要枚举 / 遍历 / 检索以尝试所有可能性。常使用迭代、搜索等算法求解，优化主要为记忆化、剪枝。循环枚举循环是最简单的枚举方案。我们将基于几个例题，讲解循环枚举的思路，并简介几种优化：基于数学的优化。基于剪枝的优化。技巧：打表法。有一个 $n \times m$（$n,m \le 5000$）的棋盘，求其方格包含多少个（四边平行于坐标轴的）正方形和长方形。本题中，长方形中不包括正方形。样例输入2 3样例输出8 10样例解释如图，正方形一共 $8$ 个，长方形 $10$ 个。正方形中，边长为 $1$ 的 $6$ 个，边长为 $2$ 的 $2$ 个；长方形中，$1 \times 2$ 的 $4$ 个，$1 \times 3$ 的 $2$ 个，$2 \times 1$ 的 $3$ 个，$2 \times 3$ 的 $1$ 个。四个参数可以确定一个长方形：左下顶点坐标 $(x_1, y_1)$ 和右上顶点坐标 $(x_2, y_2)$，也可以理解为“左右下上” $(x_1, x_2, y_1, y_2)$。思路 0：用四重循环，直接枚举 $4$ 个参数，即两横边两竖边。int rectangle = 0, square = 0; for (int x1 = 1; x1 <= n; ++x1) for (int y1 = 1; y1 <= m; ++y1) for (int x2 = x1 + 1; x2 <= n; ++x2) // x2 从 x1 + 1 起，不重复不遗漏 for (int y2 = y1 + 1; y2 <= m; ++y2) { // 同上 if (x2 - x1 == y2 - y1) ++square; // 正方形，两边长相等 else ++rectangle; // 长方形 }为什么是 $x_2$ 从 $x_1 + 1$ 开始，$y_2$ 从 $y_1 + 1$ 开始枚举？如果 $x_1 > x_2$，那么 $x_1$ 就不再是左侧了，$x_2$ 才是左侧（左图）。如果 $x_1 = x_2$，那么无法构成长方形，退化为一根线段（中图）。只有 $x_1 < x_2$ 才能正常构成长方形（右图）。$y_1$ 和 $y_2$ 同理。所以，这样可以保证不重复地遍历所有的方形。根据循环的范围可知，我们也没有遗漏任何的方形，时间复杂度 $O(n^2 m^2)$——似乎有点慢，但是至少答案正确了。为了减少枚举量，可以考虑拆解问题，尝试解决简单问题，例如，固定其中一个顶点为 $(x, y)$，计算长方形与正方形的个数。思路 1：以上图中的点 $(3, 4)$ 为例（左下角为原点），位于同一对角线（图中虚线）上所有点均可构成正方形。除自身所在行列外，所有其它点均可与其构成长方形，故直接得长方形数为 $n \times m - 正方形数$。从右图可以看出，每一个长方形或正方形均被其 $4$ 个顶点各计算一次，因此，最终答案需要除以 $4$。斜线上的格点个数为多少呢？若顶点在长方形顶点，格点个数为长方形的短边长，即 $\min \{n, m\}$。否则，以顶点为界分为 $4$ 份。每份都这样计算，得到正方形个数为 $\min \{x, y\} + \min \{n - x, y\} + \min \{x, m - y\} + \min\{n - x, m - y\}$。因此，枚举 $(x, y)$ 后，可在 $O(1)$ 时间内计算答案，求和。总时间复杂度 $O(nm)$，直接优化掉一个 $O(nm)$。能否更快？思路 2：每一个长方形重复了 $4$ 次，能否不重复呢？结合思路 0 可知，只需考虑右上角为 $(x, y)$ 的情况，因此计算斜线上的顶点时，只需要向左下角一个方向扩展。先算 $4$ 个方向，再除以 $4$，可谓是画蛇添足啊。for (int x = 1; x <= n; ++x) for (int y = 1; y <= m; ++y) { int tmp = min(x, y); square += tmp, rectangle += x * y - tmp; }当然，这里选择固定其它角也是等价的，但是固定右上角最简单。注意：这里的原点是在左下角，列是 $x$，行是 $y$。如果选择左上角作为原点，那么枚举的就是长方形右下角。思路 3：枚举边长 $(a, b)$。题目变为在 $n \times m$ 的长方形中能放置多少个 $a \times b$ 的方形。注意 $a, b$ 有序，即 $a \times b$ 和 $b \times a$ 不等价。$n$ 列中选连续 $a$ 列有 $[1, a], [2, a + 1], \cdots , [n - a + 1, n]$，共 $n - a + 1$ 种可能；$m$ 列中选连续 $b$ 行构成方形，同理有 $m - b + 1$ 种情况。所以 $n \times m$ 的长方形中可容纳 $(n - a + 1) \times (m - b + 1)$ 个 $a \times b$ 的方形。根据上面的算法，我们知道想要容纳 $a \times b$ 的方形需要两步：确定 $a$ 和确定 $b$。对于每个 $a$，有 $n - a + 1$ 种方案；对于每个 $b$，有 $m - b + 1$ 种方案，因此总的方案数是 $(n - a + 1) \times (m - b + 1)$。也就是说，我们只需要将确定 $a$ 的方案数和确定 $b$ 的方案数乘起来，就可以得到总的方案数了。那么，如果步骤更多，总方案数仍然等于所有步骤的方案数的乘积吗？答案是肯定的。因此，我们有：乘法原理：完成一个工程需要分 $n$ 个步骤，$a_i$（$1 \le i \le n$）代表第 $i$ 个步骤的不同方法数目，那么完成这件事共有 $S = \prod \limits_{i = 1}^{n} a_i = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。类似地，还有：加法原理：完成一个工程可以有 $n$ 类办法，$a_i$（$1 \le i \le n$）代表第 $i$ 类方法的数目，那么完成这件事共有 $S = \sum \limits_{i = 1}^{n} = a_1 + a_2 + \cdots + a_n$ 种不同的方法。上述两种定理构成了组合数学的基石，我们将在几周后系统性地学习组合数学。乘法原理与加法原理极其容易混淆，请各位仔细甄别。for (int a = 1; a <= n; ++a) for (int b = 1; b <= m; ++b) { if (a == b) square += (n - a + 1) * (m - b + 1); else rectangle += (n - a + 1) * (m - b + 1); }只有长等于宽，才能构成正方形；其余均为长方形。因此，如果 $a = b$，就计入正方形。使用循环枚举 $a, b$，累加求和即可。思路 4：沿用刚才乘法原理的思想，枚举量还可进一步减少。在 $n \times m$ 的长方形中方形个数，等价于在 $m + 1$ 条行线中选首尾 $2$ 行，在 $n + 1$ 条列线中选首尾 $2$ 列所围成的方形数目。在 $n + 1$ 条列线中选 $2$ 条围长方形，左列线有 $n + 1$ 种情况；右列线不能和左列线重复，只有 $n$ 种情况。将它们乘起来。由于重复统计（“左右”和“右左”），还要将乘积除以 $2$，因此列线的组合有 $\dfrac{n \times (n + 1)}{2}$ 种可能。同理，行线的组合有 $\dfrac{m \times (m + 1)}{2}$ 种可能，所以一共有 $\dfrac{n \times (n + 1) \times m \times (m + 1)}{4}$ 个方形。借助思路 3，去掉其中的正方形。时间复杂度降到 $O(\min \{n, m\})$。烤鸡时需要加入 $10$ 种配料，每种配料可放 $1$ 到 $3$ 克。美味程度是所有配料质量之和。给出一个美味程度 $n$（$n \le 5000$）按照字典序输出配料搭配的方案数量和所有的搭配方案。如果 $n$ 超过 $30$ 请输出 $0$。样例输入11样例输出10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1思路 1：由于这题要求输出所有的具体方案，所以公式不管用了，那就硬着头皮写暴力枚举吧。首先，每一种调料至少为 $1$，所以必有 $n \ge 10$。同样，每一种调料最多为 $3$，所以必有 $n \le 30$。——共有 $10$ 种调料，所以 $10$ 重循环即可解决。for (int a = 1; a <= 3; ++a) for (int b = 1; b <= 3; ++b) for (int c = 1; c <= 3; ++c) for (int d = 1; d <= 3; ++d) for (int e = 1; e <= 3; ++e) for (int f = 1; f <= 3; ++f) for (int g = 1; g <= 3; ++g) for (int i = 1; i <= 3; ++i) for (int j = 1; j <= 3; ++j) if (a + b + c + d + e + f + g + h + i + j == n) ++ans; cout << ans << endl; for (int a = 1; a <= 3; ++a) for (int b = 1; b <= 3; ++b) for (int c = 1; c <= 3; ++c) for (int d = 1; d <= 3; ++d) for (int e = 1; e <= 3; ++e) for (int f = 1; f <= 3; ++f) for (int g = 1; g <= 3; ++g) for (int i = 1; i <= 3; ++i) for (int j = 1; j <= 3; ++j) if (a + b + c + d + e + f + g + h + i + j == n) cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << ' ' << f << ' ' << g << ' ' << h << ' ' << i << ' ' << j << endl;太丑陋了。不过，不能上公式，不代表不能用其他方法优化了。思路 2：如果 $a + b + c + d + e$ 已经超过 $n$，那么 $f, g, h, i, j$ 无论如何取值，都不可能使得答案再等于 $n$ 了。因为 $f, g, h, i, j$ 至少取 $1$，所以 $a + b + c + d + e$ 达到 $n - 3$ 或以上的时候，就已经没有任何的可能性了。基于上述事实，可以构造出剪枝算法：限定每一个数的范围。for (int a = max(1, n - 27); i <= min(3, n - 9); ++a) for (int b = max(1, n - 24 - a); i <= min(3, n - 8 - a); ++b) for (int c = max(1, n - 21 - a - b); i <= min(3, n - 7 - a - b); ++c) for (int d = max(1, n - 18 - a - b - c); i <= min(3, n - 6 - a - b - c); ++d) for (int e = max(1, n - 15 - a - b - c - d); i <= min(3, n - 5 - a - b - c - d); ++e) for (int f = max(1, n - 12 - a - b - c - d - e); i <= min(3, n - 4 - a - b - c - d - e); ++f) for (int g = max(1, n - 9 - a - b - c - d - e - f); i <= min(3, n - 3 - a - b - c - d - e - f); ++g) for (int h = max(1, n - 6 - a - b - c - d - e - f - g); i <= min(3, n - 2 - a - b - c - d - e - f - g); ++h) for (int i = max(1, n - 3 - a - b - c - d - e - f - g - h); i <= min(3, n - 1 - a - b - c - d - e - f - g - h); ++i) for (int j = max(1, n - a - b - c - d - e - f - g - h - i); i <= min(3, n - a - b - c - d - e - f - g - h - i); ++j) { li[ans][1] = a; li[ans][2] = b; li[ans][3] = c; li[ans][4] = d; li[ans][5] = e; li[ans][6] = f; li[ans][7] = g; li[ans][8] = h; li[ans][9] = i; li[ans][10] = j; ++ans; }虽然更丑陋了。但是效率更高了，赢！洛谷 P1618。将 $1, 2, \cdots, 9$ 共 $9$ 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 $A : B : C$（ $A < B < C < 10^9$），试求出所有满足条件的三个三位数，若无解，输出 $\tt{No!!!}$。样例输入1 2 3样例输出192 384 576 219 438 657 273 546 819 327 654 981已知只要枚举第一个三位数，从 $123$ 枚举到 $987$。就可以根据比例确定另两个（不一定存在）最后检验得到的结果是否总共同时具有 $9$ 个不同数位。bool b[10]; long long a, b, c, x, y, z, cnt; // 全局变量 cnt 自动初始化为 0 void go(int x) { // 分解三位数到桶里 b[x % 10] = true; b[x / 10 % 10] = true; b[x / 100] = true; } bool check(int x, int y, int z) { memset(b, 0, sizeof(b)); if (y > 999 || z > 999) return false; go(x), go(y), go(z); for (int i = 1; i <= 9; ++i) if (!b[i]) return false; return true; } int main() { cin >> a >> b >> c; for (x = 123; x <= 987; ++x) { if (x * b % a || x * c % a) continue; y = x * b / a, z = x & c / a; if (check(x, y, z)) cout << x << ' ' << y << ' ' << z << endl, ++cnt; } if (!cnt) cout << "No!!!" << endl; return 0; }子集枚举有时候问题可以归纳为这样一个情况：在若干元素当中，选择其中一些以达成特定条件。我们可以像“烤鸡”一题中那样，将每一个元素视为有两种情况：选或不选。然后使用多重循环解决问题。对于这种特殊的问题，可以使用子集枚举。注意到每一个元素只有两种状态。联想到二进制。用第 $i$ 个二进制位来表达第 $i$ 个元素的取舍。习惯上，$1$ 表示选取，$0$ 表示丢弃。那么一个 $n$ 位二进制整数就可以表达 $n$ 个元素的取舍，即：$25 = $ $= \{0, 3, 4\}$。请思考：为什么二进制的最右边的一位，代表第一个元素呢？可用 C++ 自带的位运算符，轻松实现集合的各项运算。上表中出现了新的运算符，用于操作一个整数中的二进制位，我们称其为位运算符。常见位运算符有以下几种：按位与：用符号 & 表示，a & b 表示将 $a$ 与 $b$ 的每一个二进制位都进行与运算，即两个数位均为 $1$ 时结果为 $1$，否则为 $0$。数学上写作 $\text{and}$。按位或：用符号 | 表示，a | b 表示将 $a$ 与 $b$ 的每一个二进制位都进行或运算，即两个数位均为 $0$ 时结果为 $0$，否则为 $1$，数学上写作 $\text{or}$。按位异或：用符号 ^ 表示，a ^ b 表示将 $a$ 与 $b$ 的每一个二进制位都进行异或运算，即两个数位不同时结果为 $1$，否则为 $0$，数学上写作 $\text{xor}$。按位非：用符号 ~ 表示，~a 表示将 $a$ 的每一个二进制位都进行取反运算，即当前位为 $1$ 时改为 $0$，当前位为 $0$ 时改为 $1$，数学上写作 $\text{not}$。左移：用符号 << 表示，a << b 表示将 $a$ 的二进制位全部向左移动 $b$ 位。右移：用符号 >> 表示，a >> b 表示将 $b$ 的二进制位全部向右移动 $b$ 位。位运算符的优先级非常低，也就是说，在语句中常常是先进行其他运算，再进行位运算，因此一定要勤加括号。这种二进制表示法又称状态压缩。之后还会深入学习一种基于状态压缩的算法——状态压缩动态规划。有了二进制表示后，就可以通过 for 循环遍历 $0$（全 $0$，即空集）到 $2n - 1$（全 $1$，即全集）的所有整数，得到所有可能的子集。int u = 1 << n; // u = 2 ^ n, u - 1 即为全集 for (int s = 0; s < u; ++s) // 枚举所有子集 [0, u) if (/* 满足题设条件 */) { // 进行统计 }优点：非常简单方便，集合运算可以基于整数运算 $O(1)$ 实现。限制：元素个数不能太多。一般不超过 $20$ 个。洛谷 P1036。从 $n$（$n \le 20$）个整数中任选 $k$ 个整数相加，求有多少种选择情况可以使和为质数。样例输入4 3 3 7 12 9样例输出1样例解释选 $3 + 7 + 19 = 29$，一共只有一种。进行子集枚举之后，求和做质数判定。题目要求选 $k$ 个整数，且和为质数。所以判定条件就是：二进制表示中恰好包含 $k$ 个 $1$。将对应元素取出后，使用质数判定算法发现是质数。bool eval(unsigned int s) { int sum = 0; for (int i = 0; i < n; ++i) if (s & (1 << i)) sum += a[i]; // 如果第 i 个元素在 s 中，求和 return is_prime(sum); // 质数判定 } unsigned int u = 1 << n; // u = 2 ^ n, u - 1 即为全集 for (unsigned int s = 0; s < u; ++s) // 枚举所有子集 [0, u) if (__builtin_popcount(s) == k && eval(s)) // 恰好包含 k 个 1 且通过质数判定 ++ans; // 统计上述代码中出现了一个新的数据类型 unsigned int，表示无符号整数。不同于 int，unsigned int 的最高位也代表一个数值位（int 的最高位是符号位，$0$ 为正数，$1$ 为负数），因此 unsigned int 总是表示一个非负数，范围在 $[0, 2^{32} - 1]$ 之间。还有一个新的函数 __builtin_popcount()，是 GCC 编译器提供的内置函数，用于计算一个无符号整数的二进制表示中 $1$ 的个数。例如，__builtin_popcount(x) 表示计算无符号整数 $x$ 的二进制表示中 $1$ 的个数。事实上，__builtin_popcount() 函数只能计算无符号整数，但现代编译器通常选择将有符号整数转为无符号整数，然后再进行调用。因此，上面的代码中如果将变量 $s$ 以 int 类型定义，也不会影响最终的结果，但为了保证教学代码的规范，此处使用 unsigned int。排列枚举给定 $n$（$1 \le n \le 9$），输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列。所谓全排列，指将 $1 \sim n$ 所有数字不重复、不遗漏地构成数列的所有可能情况。要求按字典序输出。样例输入3样例输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1第一个排列当然是 $1, 2, 3, \cdots , n$。如何生成第二个排列呢？我们通常使用的十进制数，可以认为是一种特殊的排列：允许各位数字可以相同。在十进制中，生成下一个排列等价于 $+1$。十进制数如何处理 $+1$ 呢？可以近似写作如下算法：令当前位为最低位。令当前位 $+1$。如果结果为 $10$，则产生进位，当前位前移，转到第 2 步。否则结束。再回到全排列。全排列要求每一项都必须不同，所以可以理解为每一次 $+1$ 都会产生进位。于是问题就变为，需要进多少位？进位之后，高位仍然是可以保证不变的。而进位则需要将当前位 $p$ 替换为后缀中大于 $p$ 的最小值 $q$。如下图：其中 $p$ 是大于 $q$ 的最小元素。于是得到代码：bool next_permutation(int a[], int n) { int p, q; for (p = n - 1; p >= 1 && a[p] > a[p + 1]; --p); // 寻找单调递减后缀 if (p <= 0) return false; // 已经是最后一个排列了 for (int i = p + 1, j = n; i <= j; ++i, --j) swap(a[i], a[j]); // 翻转单调递减后缀为递增 for (int i = p + 1; i <= n; ++i) if (a[i] > a[p]) { // 找到最小大于 p 的值 q = i; break; } swap(a[p], a[q]); return true; // 生成了新的排列 }其实万能的 STL 里面也是有这个算法的。#include <algorithm> // 头文件 bool next_permutation(begin, end); // 函数原型和大多数 STL 函数一样，begin 指数组首地址，end 指数组末地址 $+1$。do { for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; } while (next_permutation(a + 1, a + n + 1));单次调用 next_permutation() 的时间复杂度为 $O(n)$，一共有 $O(n!)$ 个可能的排列，总复杂度为 $O(n \times n!)$。对于本题而言，这个复杂度是可以接受的。对于其他问题而言，一定要根据题目需要，设计合适的剪枝算法。洛谷 P1618（是的上面已经出现过一次了）。将 $1, 2, \cdots, 9$ 共 $9$ 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 $A : B : C$（ $A < B < C < 10^9$），试求出所有满足条件的三个三位数，若无解，输出 $\tt{No!!!}$。样例输入1 2 3样例输出192 384 576 219 438 657 273 546 819 327 654 981这里给出另外一种解法：直接枚举三个三位数再检验，每次变排列。for (int i = 1; i <= 9; ++i) a[i] = i; do { x = a[1] * 100 + a[2] * 10 + a[3]; y = a[4] * 100 + a[5] * 10 + a[6]; z = a[7] * 100 + a[8] * 10 + a[9]; if (x * b == y * a && y * c == z * b) cout << x << ' ' << y << ' ' << z << endl, ++cnt; } while (next_permutation(a + 1, a + 10)); if (!cnt) cout << "No!!!" << endl;总结求解问题：在若干种选项中，寻找可行解或最优解的问题。暴力枚举：遍历所有选项解决求解问题的手段。循环枚举：数学优化，剪枝优化，打表法。子集枚举：二进制状态压缩，__builtin_popcount()。排列枚举：排列生成算法，next_permutation()。学而时习之，不亦说乎。学而不思则罔，思而不学则殆。
在 C++ 中，64 位无符号整型（即 unsigned long long）最大只能表示到 $2^{64} - 1 = 18446744073709551615$，而有些题目需要用到更大的整数类型，位数可能高达几十万，怎么办呢？我们只能通过数组来模拟实现高精度的运算，本章将介绍高精度整数的加法、减法以及乘法。在学习如何对高精度的数进行运算之前，我们首先来看一看，应该如何读取大整数。高精度的读入我们可以用一个数组来保存整个高精度整数，并记录高精度整数的长度 $len$ 。为了便于之后的计算，我们都会在读入的时候把这个整数倒置。也就是说 $a_0$ 保存个位数字，$a_1$ 保存十位数字……string num; cin >> num; int a[105]; int len = num.size(); for (int i = 0; i < len; ++i) a[i] = num[len - 1 - i] - '0'; // 注意这里要减去 '0'，把字符转换为整数当然，有时题目会出现读入数据中的高精度整数需要一位数一位数读入的情况，这样的话读入就更方便了。例如对于数据：5 2 5 3 2 1就表示一个长度为 $5$ 的高精度整数 $25321$，可以用如下的代码来读入：int a[105], len; cin >> len; for (int i = len - 1; i >= 0; --i) cin >> a[i];高精度的输出输出一个高精度的数就非常容易了，直接把数组中的元素倒序输出就可以啦。for (int i = len - 1; i >= 0; --i) cout << a[i]; cout << endl;为什么要倒序存储呢？别急，学到后面具体的高精度运算方法以后你就会明白了。接下来，我们来学习如何进行高精度加法运算。高精度加单精度什么是单精度整数？单精度整数就是一个与高精度整数对应的概念，表示可以用一个整型（int 或 long long）变量存储的整数。如何进行计算呢？我们回顾一下竖式加法： 2 3 1 1 9 +) 1 ------------ 2 3 1 1 10 2 3 1 1 9 +) 1 ------------ 2 3 1 2 0怎样计算呢？首先，我们要把加的数和高精度整数的个位对齐。之后，我们让小整数和高精度整数的个位相加，最后再处理进位操作就可以了。接下来，我们看一个更为特殊的例子： 2 3 1 1 9 +) 99 ------------- 2 3 1 1 108 2 3 1 1 9 +) 99 ------------- 2 3 1 11 8 2 3 1 1 9 +) 99 ------------- 2 3 2 1 8我们总结一下计算过程：将要加的数加到高精度数组下标为 $0$ 的位置上，当前指向这一位；让下一位数加上当前位上的数除以 $10$ 的商，当前位上的数对 $10$ 取模；向后移动一位，继续执行第二步操作。高精度加单精度的关键代码如下：int a[105], x, len; // 将高精度读入到 a，倒序防止处理进位时遇到问题 // 高精度的位数记为 len // 将单精度数读入到 x a[0] += x; for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[i] %= 10; }代码实现本节课，我们将实现高精度加单精度的代码。代码初始部分已读入一个高精度整数，以 string 的形式储存在 $num$ 中，然后读入一个 int 类型数储存在变量 $x$ 里。首先，我们求出 $num$ 的长度，赋值给变量 $len$，然后把 $num$ 的每一位数字倒序放入数组 $a$ 中。#include <iostream> #include <string> using namespace std; string num; int x, len, a[105]; // 多开一些预留进位 int main() { cin >> num >> x; len = num.size(); for (int i = 0; i < len; ++i) a[i] = num[len - i - 1] - '0'; a[0] += x; for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[len] %= 10; ++len; } for (int i = len - 1; i >= 0; --i) cout << a[i]; cout << endl; return 0; }现在，整个程序就已经完成了。点击运行，输入一个很大的数和一个较小的数（较小的数不能超出 int 的范围），看看他们两个相加的和是多少吧。999999999999999999999999999 233高精度加高精度前面我们学习了如何计算高精度整数加上单精度整数的结果。接下来，我们来看一看如何计算高精度整数加上高精度整数的运算结果。我们回忆一下加法的竖式运算: 8 3 2 5 1 +) 4 2 7 9 ----------- 8 7 5 3 0我们是怎样一步步计算的呢？是不是首先计算右数第一位的两个数的和，然后处理进位；然后计算进位和第二位两个数的和，然后处理进位……直到处理完最高位，计算结束。接下来，我们试着用一种和之前不太一样的方法来在竖式上计算加法，首先，将两个数的最低位对齐，并计算每一位上两个数的和。 8 3 2 5 1 +) 4 2 7 9 ------------- 8 7 4 12 10之后，从第一位开始，依次处理进位。在这里，我们处理进位的方法和高精度加上单精度没有任何区别。 8 3 2 5 1 +) 4 2 7 9 ----------- 8 7 5 3 0这样，就完成了高精度加上高精度的计算。和高精度加单精度相比，唯一的不同就是求和的过程。我们这里不再是只让储存高精度的数组下标为 $0$ 的位置加上一个 $x$ 了，而是让每一位都加上另外一个高精度对应位置上的值，然后再处理进位。int a1[105], len1, a2[105], len2; // 分别读入两个高精度数，第一个数保存在 a1 里，长度为 len1，第二个数保存在 a2 里，长度为 len2 len1 = max(len1, len2); for (int i = 0; i < len1; ++i) a1[i] += a2[i]; for (int i = 0; i < len1; ++i) { a1[i + 1] += a1[i] / 10; a1[len1] %= 10; ++len1; }本节课，我们将实现两个高精度整数的加法运算。代码初始部分已读入这两个高精度整数，以 string 的形式分别储存在 $num1$ 和 $num2$ 中。并且把它们按照高精度要求倒序放入了 $a1$ 和 $a2$ 数组，并且把长度赋值给了 $len1$ 和 $len2$。接下来我们准备做加法，在还没进位的情况下，和的长度是原来两个数长度的较大者，然后我们把每一位对应相加。#include <iostream> #include <string> using namespace std; string num1, num2; int a1[105], a2[105], len1, len2; int main() { cin >> num1 >> num2; len1 = num1.size(); for (int i = 0; i < len1; ++i) a1[i] = num1[len1 - i - 1] - '0'; len2 = num2.size(); for (int i = 0; i < len2; ++i) a2[i] = num2[len2 - i - 1] - '0'; len1 = max(len1, len2); for (int i = 0; i < len1; ++i) a1[i] += a2[i]; for (int i = 0; i < len1; ++i) { a1[i + 1] += a1[i] / 10; a1[i] %= 10; } while (a1[len1]) { a1[len1 + 1] = a1[len1] / 10; a1[len1] %= 10; ++len1; } for (int i = len1 - 1; i >= 0; --i) cout << a1[i]; cout << endl; return 0; }现在点击运行，输入两个字符串表示两个高精度整数，然后看一看他们相加的结果是多少吧。当然，这两个高精度整数也不能太大，不能超出数组长度的上限。比如可以输入：9999 99998高精度减单精度在前面的课程里，我们学习了高精度加法的两种情况：高精度加单精度、高精度加高精度。那么，要如何实现高精度的减法操作呢？首先，我们来看一个高精度的整数要如何和一个单精度的整数进行减法操作。当然，我们在这一节里先不考虑高精度整数比单精度整数小的情况，也就是说结果不会是负数。我们还是从竖式减法入手，看一看应该如何进行高精度的减法操作。 5 9 2 3 4 -) 9 ------------ 5 9 2 2 5我们再来把这个过程拆解一下。首先，让高精度整数的第一位减去单精度整数: 5 9 2 3 4 -) 9 ------------- 5 9 2 3 -5这时候我们发现，减完以后的高精度整数的第一位变成了负数，需要从下一位借位。我们让下一位减 $1$，当前这一位加上 $10$。 5 9 2 3 4 -) 9 ------------ 5 9 2 2 5这样就完成了高精度减单精度的运算。高精度减高精度的过程和高精度加单精度其实是非常类似的。我们来看一下计算过程:在高精度数组下标为 $0$ 的位置减去单精度整数，当前指向这一位；如果当前位上的数小于 $0$，就让当前指向的下一位减去 $1$，并让当前位加上 $10$，直到当前位上的数不小于 $0$；向前移动一位，继续执行第二步操作。除了上述过程和加法有所差异以外，最后的长度处理也与加法有所不同。进行相减操作以后，高精度整数的总长度有可能会变小，所以需要判断是否当前高精度整数的最高位已经是 $0$，如果是 $0$ 则需要让总长度减去 $1$。要注意如果减完结果就是 $0$ 了，我们需要保留这个唯一的 $0$。核心代码如下：a[0] -= x; for (int i = 0; i < len; ++i) while (a[i] < 0) --a[i + 1], a[i] += 10; while (len > 1 && a[len - 1] == 0) --len;代码实现#include <iostream> #include <string> using namespace std; string num; int x, len, a[105]; int main() { cin >> num >> x; len = num.size(); for (int i = 0; i < len; ++i) a[i] = num[len - i - 1] - '0'; a[0] -= x; for (int i = 0; i < len; ++i) while (a[i] < 0) --a[i + 1], a[i] += 10; while (len > 1 && a[len - 1] == 0) --len; for (int i = len - 1; i >= 0; --i) cout << a[i]; cout << endl; return 0; }高精度减高精度刚才我们学习了如何计算一个高精度整数和单精度整数的减法。接下来，我们看看要如何计算一个高精度整数和一个高精度整数的减法操作。首先有一个高精度减法的特殊情况：如果第一个数小于第二个数，我们要怎么去计算它们两个的差呢？我们可以在结果的最前面加上一个负号，并交换这两个数，这样最终结算的结果就和我们期望的一致了。例如，我们要计算 $2 - 5$ 的结果，应该为 $-3$，那么我们首先写出一个负号：-然后计算 $5 - 2$ 的值并输出:-3比较两个高精度数大小可以先比较两个数的位数，位数不同时位数少的小，位数相同时可以从最高位开始比较，遇到某一位不同，比较小的就小，此时其实比较的也是两个数本身的字典序，字典序小的就小。这样，我们就可以把问题简化了。现在我们需要解决的是，如何计算两个高精度整数的减法结果，保证前一个数不小于后一个数。和加法一样，我们继续用竖式来分析这个过程： 5 2 3 1 4 -) 9 7 6 8 --------------- 4 2 5 4 6我们参考前面高精度减单精度的方法，首先，让两个高精度整数的最低位对齐，之后让它们每一位的结果等于第一个数该位置减去第二个数该位置的结果。 5 2 3 1 4 -) 9 7 6 8 --------------- 5 -7 -4 -5 -4然后，从最低位开始，如果发现当前位上的数小于 $0$，就让当前位加上 $10$，更高的一位减去 $1$。 5 2 3 1 4 -) 9 7 6 8 --------------- 5 -7 -4 -6 6 5 2 3 1 4 -) 9 7 6 8 --------------- 5 -7 -5 4 6 5 2 3 1 4 -) 9 7 6 8 --------------- 5 -8 5 4 6 5 2 3 1 4 -) 9 7 6 8 --------------- 4 2 5 4 6通过刚才这个例子，我们基本对减法的借位处理有了一个初步的印象。其实，借位过程跟我们前面实现的高精度减单精度的借位处理过程是完全一样的。不同之处在于，我们需要先对两个数的每一位进行减法操作，并且在最后由于长度的减少值可能不止 $1$，所以需要不断地判断最高位是否已经被减到 $0$。并且，因为每一位上的数均在 $0 \sim 9$ 之间，所以之前的 while (a1[i]<0) 写成 if (a1[i] < 8) 也可以。参考代码如下：#include <iostream> #include <algorithm> #include <string> using namespace std; string num1, num2; int a1[105], a2[105], len1, len2; bool sgn; // 标记正负 bool cmp(string &a, string &b) { // 自定义排序 // 使用引用传参，防止传参时复制字符串浪费大量时间 if (a.size() != b.size()) return a.size() < b.size(); return a < b; } int main() { cin >> num1 >> num2; if (cmp(num1, num2)) { sgn = true; // num1 更小，控制输出负号 swap(num1, num2); // 交换 } len1 = num1.size(); for (int i = 0; i < len1; ++i) // 字符串转换为数字数组 a1[i] = num1[len1 - i - 1] - '0'; len2 = num2.size(); for (int i = 0; i < len1; ++i) // 字符串转换为数字数组 a2[i] = num2[len2 - i - 1] = '0'; for (int i = 0; i < len1; ++i) a1[i] -= a2[i]; // 相减 for (int i = 0; i < len1; ++i) // 借位 if (a1[i] < 0) --a1[i + 1], a1[i] += 10; while (len1 > 1 && a1[len1 - 1] == 0) --len; // 重新验长度 if (sgn) cout << '-'; for (int i = len1 - 1; i >= 0; --i) cout << a1[i]; // 输出 cout << endl; return 0; }高精度乘单精度前面我们已经学习了如何对高精度整数进行加法和减法运算。接下来，我们来学习一个相比于之前复杂一些的运算——乘法运算。为了便于理解，我们还是先从高精度乘以单精度入手，看一看它的计算过程。我们将高精度乘以单精度的竖式列出来： 5 2 4 ×) 3 ---------- 1 5 7 2还记得我们是怎样进行竖式乘法运算的么？我们会依次地计算下面的数和上面所有数的乘积，并处理进位操作。接下来，我们把这个过程一步步拆解来看。首先，计算每一位和 $3$ 的乘积。 5 2 4 ×) 3 ----------- 15 6 12处理最后一位进位： 5 2 4 ×) 3 ----------- 15 7 2倒数第二位不需要进位。处理倒数第三位进位： 5 2 4 ×) 3 ----------- 1 5 7 2我们总结一下高精度乘以单精度的计算过程。将单精度整数乘到高精度整数的每一位上；从最低位开始，依次向前处理进位，这个过程和加法的一致；处理最终结果长度增加的情况，这个过程也和加法的一致。核心代码如下：// 第一步，计算每一位的乘积 for (int i = 0; i < len; ++i) a[i] *= x; // 第二步，处理进位 for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[i] %= 10; } // 第三步，处理长度增加的情况 while (a[len]) { a[len + 1] += a[len] / 10; a[len] %= 10; ++len; }代码实现#include <iostream> #include <string> using namespace std; string num; int x, len, a[105]; int main() { cin >> num >> x; len = num.size(); for (int i = 0; i < len; ++i) a[i] = num[len - i - 1] - '0'; for (int i = 0; i < len; ++i) a[i] *= x; for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[i] %= 10; } while (a[len]) { a[len + 1] += a[len] / 10; a[len] %= 10; ++len; } for (int i = len - 1; i >= 0; --i) cout << a[i]; cout << endl; return 0; }高精度乘高精度前面的课程里，我们学习了如何计算高精度乘以单精度的结果。接下来，我们就要学习本章的最后一部分内容——高精度乘高精度。相比于前面学过的高精度加法、高精度减法、高精度乘以单精度这几类运算，高精度乘以高精度会更为复杂一些。和前面每种计算方法一样，我们还是从竖式运算入手，看一看整个计算过程应该怎样进行。观察每列不难发现，若不考虑进位，$a_i \times b_j$ 的贡献全都在中间产物的第 $i + j$ 位上！因此可以先算出贡献，最后处理进位.参考代码如下：for (int i = 0; i < len1; ++i) for (int j = 0; j < len2; ++j) a[i + j] += a1[i] * a2[j]; len = len1 + len2 - 1; // 思考一下，为什么相乘后的长度 len = len1 + len2 - 1 ？ for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[i] %= 10; } while (a[len]) { a[len + 1] += a[len] / 10; a[len] %= 10; ++len; }代码实现#include <iostream> #include <string> using namespace std; string num1, num2; int a1[105], a2[105], len1, len2, a[205], len; int main() { cin >> num1 >> num2; len1 = num1.size(); for (int i = 0; i < len1; ++i) a1[i] = num1[len1 - i - 1] - '0'; len2 = num2.size(); for (int i = 0; i < len2; ++i) a2[i] = num2[len2 - i - 1] - '0'; for (int i = 0; i < len1; ++i) for (int j = 0; j < len2; ++j) a[i + j] += a1[i] * a2[j]; len = len1 + len2 - 1; for (int i = 0; i < len; ++i) { a[i + 1] += a[i] / 10; a[i] %= 10; } while (a[len]) { a[len + 1] += a[len] / 10; a[len] %= 10; ++len; } for (int i = len - 1; i >= 0; --i) cout << a[i]; cout << endl; return 0; }请同学们边写边想，思路很重要，代码也很重要。
请注意，如无特殊说明，本文默认序列的下标从 $1$ 开始。在现实生活中，经常需要对事物或信息进行排序。具体而言，我们收集到的数据大多是无序的，而我们需要有序的结果作为产出或作为后续步骤的输入。有序性是一个很好的规律。例如，若一个序列是有序的，我们就可以在 $O(1)$ 时间内查找第 $k$ 小的元素，但对于无序序列就很困难。将无序的序列转变为有序，即是排序问题。本讲义将介绍若干种排序算法。我们将会看到，不同算法均有各自适应的应用场景，并非只需掌握一种即可。计数排序洛谷 P1271。学校正在选举学生会成员，有 $n$（$n \le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（ $m \le 2 \times 10^6$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字，求出排序后的选票编号。样例输入2 5 2 2 5 2 2 2 1 2样例输出1 2 2 2 2 2 2 2 5 5显然，题意即是经典的排序问题。输入无序序列，输出有序序列。我们可以考虑现实中如何（匿名）计票：取出一张票（可以按照任意顺序，一般按照收集顺序即可）。将其放入与其编号相同的票箱，且该堆的计数 $+1$。例如上述样例，有：因为是匿名计票，所以选票本身的特殊性并不重要，表格中实际有效的只有总计数值。得到有序序列，我们只需要按照票箱号从小到大从票箱中拿出选票即可。此时我们有 $1$ 张 #1、$7$ 张 #2 和 $2$ 张 #5，因此序列为：$$ \text{1 | 2 2 2 2 2 2 2 | | | 5 5} $$即为所求。注意中间的隔断“$\text{|}$”：我们依然可以“尝试”从 $3$、$4$ 号票箱取票，但因为是空的，所以没有取出内容。使用数组模拟票箱。根据刚才的结论，我们只需要记载票箱内的选票数即可。int a[1010] = {0};接下来，我们按照输入顺序读取每一张票，并置入票箱：for (int i = 1; i <= m; ++i) cin >> tmp, ++a[tmp];最后，再按照票箱编号顺序取出所有选票（为了表述清晰，我们使用循环变量 $i$ 代表选票，$j$ 代表票箱）：for (int j = 1; j <= n; ++j) for (int i = 1; i <= a[j]; ++i) cout << j << ' ';计数排序顾名思义，即统计每一个元素出现的次数，再按照顺序依次排列。数列中的元素就是“票”而一个与元素取值范围相符的数组就是“票箱”。记 $n$ 为数列长度，$m$ 为取值范围。需要 $O(n)$ 的时间统计每一数值出现次数。之后再用 $O(n+m)$ 的时间构造出结果数列，总时间 $O(n+m)$。另外，需要 $O(m)$ 的额外空间作为票箱。优点：当 $m$ 较小时，时间复杂度近似于 $O(n)$，性能强大。缺点：当 $m$ 远大于 $n$ 时，时空复杂度均取决于 $m$，得不偿失，且取值范围为非整数时，无法实现。当原数组的数据比较集中时，才推荐使用计数排序。计数排序的变种离散化计数排序：若能将不可表示的数据范围（双向）映射到较小的整数集合上则可以在映射后使用计数排序。这一映射过程称为离散化。桶排序：将数列按数值区间（而非具体数值）划分为若干个桶。桶内采用其他排序算法。基数排序：从低到高对每一个（$X$ 进制）位进行一次计数排序。这样，当高位有序时，所有低位均已有序。可以保证只使用X个桶。此处不要求掌握。基于交换的排序现在我们开始玩牌。你要如何整理你的手牌呢?我都是把相同的数字牌扣在桌面上来排序的！这不还是一种计数排序吗？没错，但是这样你的对手就可以通过观看牌桌上倒扣的牌堆推测你的牌型。所以你决定只通过交换的方式来排序。首先给出一些需要掌握的前置知识——逆序对。假设排序应当是从小到大，如果有一对牌，前面的那张牌比后面的那张牌数字大，那么我们称这两张牌是一个逆序对。形式化地，当一个序列 $a$ 中存在正整数 $i, j$ 使得 $i < j$ 且 $a_i > a_j$，那么 $\langle a_i, a_j \rangle$ 称为一个逆序对。基于交换的排序方法接下来我们来了解基于交换的排序方法。所谓交换，即数列元素两两比较，若顺序反了则对换二者位置。由于每一次交换逆序对数必然减少，持续交换必然可以完成排序，且具有不用到其他变量而直接在原数列中操作、额外空间复杂度为 $O(1)$ 的优点。考虑到元素两两间均需要互相比较，可以大致估计出，此类方法最坏时间复杂度均约为 $O(n^2)$。选择排序思路：$n$ 次大循环，第 $i$ 次小循环中，用小循环寻找数列中第 $i$ 小的元素。如果发现更小的数字，则交换至第 $i$ 个位置。for (int i = 1; i <= n - 1; ++i) for (int j = i + 1; j <= n; ++j) if (a[j] < a[i]) swap(a[i], a[j]);特点实现简单。每次迭代都能保证至少一个（最小）元素的位置被确定。前 $i$ 个元素有序，且为最小的 $i$ 个元素。事实上，由于前 $i - 1$ 项已经排序完毕，第 $i$ 小的元素等价于第 $i$ 项至第 $n$ 项中的最小元素。选择排序常用于 $k$ 很小时快速求解前 $k$ 大（或小）元素。冒泡排序思路：不超过 $n$ 次大循环，每次大循环按照顺序比较相邻元素并交换，直到序列有序。for (int i = 1; i <= n - 1; ++i) for (int j = 1; j <= n - i; ++j) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);特点总交换次数恰为逆序对数。每次迭代都能保证至少一个（最大）元素的位置被确定。后 $i$ 个元素有序，且为最大的 $i$ 个元素。冒泡排序常用于模拟逆序对相关的问题。插入排序思路：$n$ 次大循环，第 $i$ 次大循环将第 $i$ 个元素向前交换，直至左侧元素不大于它，或抵达数列首部。for (int i = 2; i <= n; ++i) { int cur = a[i], j; // 记录一下待插牌，等下还要放回去 for (j = i - 1; j >= 1; --j) { if (a[j] > now) a[j + 1] = a[j]; else break; } a[j + 1] = cur; }特点前 $i$ 个元素有序。排序完成之前，不能保证任何一个元素的最终位置被确定，如最小元素在数列尾部的情况。插入排序可以用来动态维护前 $k$ 大（或小）元素，单次插入时间复杂度 $O(k)$。在此场景下，第 $k + 1$ 小的元素将不会右移，而是被直接丢弃。快速排序是否存在性能比 $O(n^2)$ 更优的排序算法呢？答案是肯定的。为什么基于交换的排序需要 $O(n^2)$ 时间？因为最坏情况下任意两个不同元素都需要比较，共 $\dfrac{n(n-1)}{2}$ 次。是否可以减少必须的比较次数呢？选择排序，每一次迭代确定一个元素的位置，但是所有已确定元素均在左侧，对右侧没有指导意义。插入排序，每一次迭代只需要与大于自身的值比较，期望只需比较一半的元素，但是没有元素确定位置，新元素的插入导致所有更大的元素右移带来额外开销。考虑结合两者的优点，以如下数列为例：3 8 4 10 6 7 2 5 9 1尝试随机选取一个元素确认位置，我们称这个数为哨兵数：3 8 4 10 *6* 7 2 5 9 1将序列中所有比哨兵数小的数字都移动到哨兵数的左边，所有比哨兵数大的数字都移动到哨兵数的右边：3 4 2 5 1 *6* 8 10 7 9显然哨兵数左右两侧的元素不再需要任何比较。因此，对两侧的子数列分别采用相同的做法，直到数列不可再分（长度为 $0$ 或 $1$）。在最优情况下：每次选择的哨兵数均将数列对半分开，则 $O(\log n)$ 次划分后数列将不可再分。每次划分的复杂度为 $O(n)$，总复杂度 $O(n \log n)$。在最坏情况下：每次选择的哨兵数均在数列一端，则退化为选择排序算法，总复杂度 $O(n^2)$。对数前面在复杂度中提到了 $\log n$，数学上称为 $n$ 的对数。形式化地，若 $a^b = N$，则有 $b = \log_a N$，即幂指数 $b$ 称为“以 $a$ 为底 $N$ 的对数”，其中 $a$ 称作对数的底数，$N$ 称作对数的真数。当 $N > 0, a > 0$ 且 $a \neq 1$ 时，有 $\log_a a^{N} = N$。此处不作证明。因为我们每次将整个数列分为两半，上面的 $\log n$ 事实上是 $\log_2 n$。但由于大 $O$ 记号中需要省略常数，因此底数 $2$ 被略去。如果不好理解为什么是 $\log_2 n$，我们来尝试一下感性理解。我们可以估计对数函数的上界，将长度为 $10$ 的序列折半划分需要 $4$ 折（$10$ 的 $2$ 进制表示有 $4$ 位），所以 $\log_2 10 < 4$。因为 $2^{31} = 2 \ 147 \ 483 \ 648$，有 $\log_2 \ 2 \ 147 \ 483 \ 648 = 31$，可见对数函数的增长十分缓慢，相比 $O(n)$ 是一个非常优秀的复杂度。常见复杂度与数据范围此处给出一种快速排序的实现，并不存在一种在所有情况下都最优的算法。建议自行了解，并根据应用场景选择合适的实现。void qsort(int a[], int l, int r) { // 引入数组的地址 int i, j = r, flag = a[(l + r) / 2], tmp; // flag 为哨兵 do { while (a[i] < flag) ++i; // 从左找比哨兵大的数 while (a[j] < flag) --j; // 从右找比哨兵大的数 if (i <= j) { swap(a[i], a[j]); ++i, --j; } } while (i <= j); // 习惯上，上面用于分段的过程一般称作 partition if (l < j) qsort(a, l, j); if (r > i) qsort(a, i, r); }快速排序是一种基于分治法的排序算法，大多数基于分治法的算法均具有 $O(n \log n)$ 的时间复杂度。其余具有此复杂度的排序算法还有：基数排序：基于按位处理。归并排序：基于分治法。堆排序：基于数据结构。排序算法的应用养兵千日，用兵一时。排序作为重要的算法工具，可以将无序变有序，使问题更好的得到处理。STL 中的排序算法algorithm（算法）库中包含很多常用的算法，包括排序。引入头文件：#include <algorithm>使用排序功能：sort(a.begin(), a.end()); // O(n log n) sort(a.begin(), a.end(), cmp); // O(n log n)begin 和 end 被称为迭代器，表示需要排序位置的首末。cmp 是一个可选参数，应该作为函数名称出现，可以自定义排序的比较方法。STL 中还有一个常用的函数，即查找函数。find(a.begin(), a.end(), val); // O(n), 查找其中，$val$ 是需要查找的值。这个函数返回第一个匹配的元素的地址（即迭代器），若元素不存在则返回 a.end()。排序以后，可以使用以下函数：unique(a.begin(), a.end()); // O(n), 去重我们之后会学到一个新的容器 vector。我们假设需要使长度为 $n$ 的 vector $v$ 等价到数组 $a$，那么有：a（或 a + 0）$\iff$ v.begin()。a + n $\iff$ v.end()。a + n - 1 $\iff$ v.back()，即最后一个元素。v.end() - v.begin() $\iff$ $n$。find(a[x]) - a $\iff$ find(v[x]) - v.begin() $\iff$ $x$。STL 函数的调用方法： 洛谷 P1059。给出 $N$（$N \le 100$）个 $1$ 到 $1000$ 的数字，输出去重后剩余数字的个数，以及去重排序后的序列。样例输入10 20 40 32 67 40 20 89 300 400 15样例输出8 15 20 32 40 67 89 300 400解法 #1：注意到数据范围很小，可以使用计数排序。解法 #2：直接使用 STL 中的排序、去重函数：sort(a + 1, a + n + 1); int cnt = unique(a + 1, a + n + 1) - a - 1; cout << cnt << endl; for (int i = 1; i <= cnt; ++i) cout << a[i] << ' ';自定义排序如果我想排序，但不是从小到大排序，怎么办？或者，能对结构体元素进行排序吗？ sort() 函数可以增加第三个参数 cmp ，也就是自定义排序的基准。cmp 函数需要两个待排序的元素 $x$、 $y$ 作为参数。返回一个 bool 值，表示 $x$ 是否严格小于 $y$。例如实现整数从大到小排序：bool cmp(int x, int y) { return x > y; } sort(a, a + n, cmp);cmp 函数名称可以任取，保持上下一致即可。洛谷 P1093。给出 $n$（$n \le 300$）名学生的语文、数学、 英语成绩，这些学生的学号依次是从 $1$ 到 $n$。需要对这些学生进行排序。如果总分相同，则语文分数高者名次靠前；如果语文成绩还是一样的，学号小者靠前。输出排名前 $5$ 的学生学号和总分。样例输入6 90 67 89 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98样例输出6 265 4 264 3 258 2 244 1 237可以使用 STL 进行排序。构造一个结构体 student 用于存储学生的各项有用的信息（数学和英语并不重要，可以不存下来）。注意使用 cmp 来进行比较，当两个学生比较时，排名比较高的学生返回 true。#include <iostream> #include <algorithm> using namespace std; const int N = 310; int n; struct student{ int id, chinese, total; } a[N]; bool cmp(student a, student b) { if (a.total != b.total) return a.total < b.total; // 总分先定胜负 if (a.chinese != b.chinese) return a.chinese < b.chinese; // 然后比语文 return a.id < b.id; // 最后比学号 } int main() { cin >> n; for (int i = 1; i <= n; ++i) { int math, english; cin >> a[i].chinese >> math >> english; a[i].total = a[i].chinese + math + english; a[i].id = i; } sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= 5; ++i) cout << a[i].id << ' ' << a[i].total << endl; return 0; }还有参照选择排序和插入排序思路的其它解法，参见课本 P139。
A 时间旅人的困境 - C++ 基本结构while (c != 1) { if (c & 1) c = c * 3 + 1; else c >>= 1; ++ans; } cout << ans << '\n';B 完美风暴 - 数组cin >> n; for (int i = 1; i <= n; ++i) cin >> p[i]; for (int i = 1; i <= 7; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) ans += a[p[i]]; cout << ans << '\n';C 加密的日记 - 字符与字符串cin >> n; cin.ignore(numeric_limits<streamsize>::max(), '\n'); getline(cin, s); for (auto &v : s) if (v != ' ') { char base = isupper(v) ? 'A' : 'a'; v = (v - base + 26 - n) % 26 + base; } cout << s << '\n';D 图书馆管理系统 - 结构体与 STLint n, x; string op, name, author; struct book { string name, author; bool borrowed; }; map<int, book> mp; cin >> n; while (n--) { x = 0; cin >> op; if (op == "ADD") { cin >> name >> author >> x; if (name.empty() || author.empty() || !x) { cout << "Invalid\n"; break; } mp[x].name = name, mp[x].author = author; } else if (op == "QUERY") { cin >> x; if (!mp.count(x)) cout << "NotFound\n"; else { if (mp[x].borrowed) cout << mp[x].name << ' ' << mp[x].author << ' ' << x << " Borrowed\n"; else cout << mp[x].name << ' ' << mp[x].author << ' ' << x << " Available\n"; } } else if (op == "BORROW") { cin >> x; if (!mp.count(x)) cout << "NotFound\n"; else mp[x].borrowed = true; } else { cin >> x; if (!mp.count(x)) cout << "NotFound\n"; else mp[x].borrowed = false; } }E 方案 - 图的存储与遍历const int N = 1010; int t, n, m, r, u, v; vector<pair<int, long long> > g[N]; long long k, w, dis[N], ans[N], sum; void dfs(int u, int fa){ for (auto to : g[u]) { int v = to.first; long long w = to.second; if(v == fa) continue; dis[v] = dis[u] + w; dfs(v, u); } } cin >> t >> k; for (int i = 1; i <= t; ++i){ for (int j = 1; j <= n; ++j) g[j].clear(); fill(dis + 1, dis + n + 1, 0); cin >> n >> m >> r; for (int i = 1; i <= m; ++i) { cin >> u >> v >> w; g[u].emplace_back(make_pair(v, w)); g[v].emplace_back(make_pair(u, w)); } dfs(r, 0); for (int j = 1; j <= n; ++j) ans[i] = max(ans[i], dis[j]); } for (int i = 1; i <= t; ++i) sum += ans[i]; if (sum >= k) cout << "YES\n" << sum << '\n'; else { cout << "NO\n"; for (int i = 1; i <= t; ++i) cout << ans[i] << ' '; }F 血夜筝鸣 - 动态规划基础cin >> n; for (int i = 1; i <= n; ++i) for (int j = 0; j < 3; ++j) cin >> a[i][j]; for (int i = 1; i <= n; ++i) { f[i][0] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2])) + a[i][0]; f[i][1] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2])) + a[i][1]; f[i][2] = max(f[i - 1][0], f[i - 1][1]) + a[i][2]; } cout << max(f[n][0], max(f[n][1], f[n][2])) << '\n';
A 你几岁了 - 输入与输出给定一个整数 $x$，输出 $\texttt{I am } x \texttt{ years old.}$。直接输出即可。记得空格！int x; cin >> x; cout << "I am " << x << " years old.";也可以使用更直观的 printf 进行输出。int x; scanf("%d", &x); // cin >> x; printf("I am %d years old.", x);B 求和 - 循环结构给定一个整数 $n$，输出 $n$ 行，第 $i$ 行输出 $1$ 到 $i$ 的和。开一个变量 $sum$ 记录 $1$ 到 $i$ 的和，从 $1$ 循环到 $n$，每次循环更新一次 $sum$，然后输出。注意到，提示给出了 $1 + 2 + 3 + \cdots + 1000000 > 2147483647$，并且 $n \le 10^7$，这告诉我们，答案可能超出 int 的范围，需要使用 long long。由于使用 endl 的输出效率太低，题目中写清了更优的换行方式，即输出 \n。求求大家好好读读题吧。int n; long long sum; cin >> n; for (int i = 1; i <= n; ++i) { sum += i; cout << sum << "\n"; }C 渡荆门送别 - 循环结构与数组给定一个整数 $n$ 和一个序列 $a$，求序列中每个元素分别与最大值和最小值的差。首先定义两个变量 $maxn$ 和 $minn$，用于存储最大值和最小值。值得注意的是，因为 $minn$ 存储的数列中的最小值，因此需要将其初始化为一个极大值，如 $10^{18}$。同理 $maxn$ 应该初始化为一个极小值，如 $0$。输入序列 $a$ 的同时更新 $maxn$ 和 $minn$，得到序列 $a$ 中最大元素与最小元素的值。遍历两次序列 $a$，第一次输出 $maxn - a[i]$，第二次输出 $a[i] - minn$ 即可。注意到，$a_i \le 10^{18}$ ，需要开 long long。const int N = 1e6 + 10; const long long INF = 1e18; int n; long long a[N], minn = INF, maxn; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; maxn = max(maxn, a[i]); // if (a[i] > maxn) maxn = a[i]; minn = min(minn, a[i]); // if (a[i] < minn) minn = a[i]; } for (int i = 1; i <= n; ++i) cout << maxn - a[i] << ' '; cout << "\n"; for (int i = 1; i <= n; ++i) cout << a[i] - minn << ' ';D 影子字符串 - 字符串输入若干个字符串，如果之前没有出现过这个字符串就输出，否则跳过。遇到字符串 $\texttt{0}$ 结束程序。可以使用一个数组 $a$ 记录之前出现过的字符串，每次读入一个字符串 $s$ 都遍历一次 $a$。如果发现 $a[i]$ 与 $s$ 相同则表示之前出现过这个字符串，那么跳过，继续输入下一个 $s$。否则说明没有出现过，那么输出这个字符串，并且将它存到数组中即可。如果读到 $s$ 为字符串 $\texttt{0}$，那么跳出循环，结束程序。const int N = 510; string s, a[N]; int cnt; // 存储 a 中有多少个元素 bool flag; while (cin >> s) { if (s == "0") break; flag = false; // 判断 a 中是否有 s，有为 true，无为 false for (int i = 1; i <= n; ++i) if (a[i] == s) { flag = true; // 如果有就将 flag 改为 true break; } if (!flag) cout << (a[++cnt] = s); // {++cnt; a[cnt] = s; cout << s;} }E 天天爱跑步 - 综合应用一共有 $n$ 天，每签到一天可以得到相应的活跃值奖励，连续签到可以获得连续签到奖励。当连续签到天数达到以下天数时，活跃值奖励将发生如下变化。$1$ 天：由 $0$ 变为 $v_1$$3$ 天：由 $v_1$ 变为 $v_3$$7$ 天：由 $v_3$ 变为 $v_7$$30$ 天：由 $v_7$ 变为 $v_{30}$$120$ 天：由 $v_{30}$ 变为 $v_{120}$$365$ 天：由 $v_{120}$ 变为 $v{365}$$366$ 天或更多天数：均为 $v_{365}$给出连续签到奖励以及 $n$ 天的签到情况，求出 天后获得的活跃值为多少。按题意模拟即可。读入 $n$，读入六个连签奖励，接下来读入 $n$ 天的签到情况。开一个变量 $cnt$ 用于记录连续签到的天数。如果当天签到了，则给 $cnt$ 加 $1$，并且给答案加上对应的活跃值奖励，否则给 $cnt$ 归零。int n, v1, v3, v7, v30, v120, v365, x, cnt, ans; // cnt 用于记录连签天数 cin >> n >> v1 >> v3 >> v7 >> v30 >> v120 >> v365; for (int i = 1; i <= n; ++i) { cin >> x; if (x) { ++cnt; if (cnt >= 1 && cnt < 3) ans += v1; else if (cnt >= 3 && cnt < 7) ans += v3; else if (cnt >= 7 && cnt < 30) ans += v7; else if (cnt >= 30 && cnt < 120) ans += v30; else if (cnt >= 120 && cnt < 365) ans += v120; else if (cnt >= 365) ans += v365; } else cnt = 0; } cout << ans << "\n";F Function - 函数递归给定递归函数：$$ w(a, b, c) = \begin{equation} \begin{cases} 1 & a \le 0 \text{ or } b \le 0 \text{ or } c \le 0 \\ w(20, 20, 20) & a > 20 \text{ or } b > 20 \text{ or } c > 20 \\ w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c) & a < b < c \text{ and } a, b, c \in [1, 20] \\ w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1) & \text{otherwise} \end{cases} \end{equation} $$给出若干组 $a$、$b$ 和 $c$ 的值，求出 $w(a, b, c)$ 的值。注意到，由于函数中进行了大量递归，效率变得十分低下。可以发现，我们在递归时，进行了大量的重复计算。考虑记忆化。新建一个三维数组 $f$，对每组 $a$、$b$ 和 $c$，把这些重复的值记录下来，递归时发现已经计算过就直接返回，显著提升了效率。由于数据范围十分庞大，我们无法记录所有的 $a$、$b$ 和 $c$，但可以发现的是，对于超过 $20$ 的 $a$、$b$ 和 $c$，递归一次就会变为 $w(20, 20, 20)$，因此只需要记录 $1$ 到 $20$ 之间的 $f[a][b][c]$ 即可。const int N = 25; int f[N][N][N]; long long w(long long a, long long b, long long c) { if (a <= 0 || b <= 0 || c <= 0) return 1; if (a > 20 || b > 20 || c > 20) return w(20, 20, 20); if (f[a][b][c]) return f[a][b][c]; if (a < b && b < c) f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c); else f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1); return f[a][b][c]; }
A 苍穹之下 - 字符与字符串读写给定一个字符串 ，判断是否为 $\texttt{Starry}$，输出对应的字符串。$40$ 分解法按题意模拟即可。看我多贴心保底都给了 $40$ 分。读入一个字符串，判断这个字符串是否等于 $\texttt{Starry}$，等于则输出 $\texttt{We are off to see the world}$，否则输出 $\texttt{For none believe in miracles}$。$60$ 分解法与 $40$ 分解法基本相同，需要加一点小小的魔法，作用是加快 cin / cout，不过不建议在完全了解这两句代码的特性之前使用，有时可能会出一些意想不到的问题。输出只有一行，所以也可以去掉浪费大量时间的 endl。说实话我是没想到会因为这个原因挂掉 $20$ 分的，对不起各位。cin.tie(nullptr); ios::sync_with_stdio(false);$80$ 分解法注意到，$|S| \le 10^8$，这已经远超了题目所给 $2$ MB 可以容纳的范围，说明此时已经不可能存得下一个完整的字符串。可以发现，需要匹配的字符串 $\texttt{Starry}$ 只有 $6$ 个字符，那么只需要依次读入并判断前 $6$ 个字符是否相同即可。$90$ 分解法我不理解大家为啥连骗分都懒得骗。cout << "For none believe in miracles" << endl;正解我也没说输入一定只有 $6$ 个字符啊。如果输入完前 $6$ 个字符后都与 $\texttt{Starry}$ 一样，先别急着输出，考虑是否可以再读一个字符。如果可以的话，那么这同样不是合法的。const string S = "Starry"; char c; for (int i = 0; i < 6; ++i) { cin >> c; if (c != s[i]) return cout << "For none believe in miracles" << endl, 0; } if (cin >> c) return cout << "For none believe in miracles" << endl, 0; cout << "We are off to see the world" << endl;B 超链接 - 二维数组的读写与应用一共有 $N$ 个网页，编号从 $1$ 到 $N$。第 $i$ 个网页上有 $T_i$ 个超链接（你可以理解为点一下就跳转到另一个页面的按钮），点击第 $j$ 个可以访问到编号为 $A_{i, j}$ 的网页。从 $1$ 号网站开始，点击不超过两次超链接，求可以访问到的不同的网页的数量。题目要求，点击不超过两次的页面，那么可以分为点击零次、一次、两次三类。对于第一类，点击零次，也就是我们的出发页面 $1$。对于第二类，点击一次，也就是页面 $1$ 上超链接指向的所有页面。对于第三类，点击两次。点击两次的页面，都是可以从点击一次的页面，再经过一次点击到达。题目已经给出，我们应当开一个二维数组存储超链接的信息，第一维 $i$ 表示这是第 $i$ 个页面上的超链接，第二维 $j$ 表示这是页面 $i$ 上的第 $j$ 个超链接。假如我们开了二维数组 $A[][]$ 用于存储超链接，那么 $A[i][j]$ 存储的就是第 $i$ 个页面上的第 $j$ 个超链接指向的页面编号。考虑这样一种做法：每访问到一个之前没访问过的页面，我们就给答案加上 $1$。因为我们从页面 $1$ 开始，所以无论如何都会访问至少一个页面，因此用于统计答案的变量应初始化为 $1$。对于只点击一次就访问到的页面，我们只需要枚举页面 $1$ 指向的页面即可。接下来考虑点击两次到达的页面。可以想到，点击两次到达的页面一定是由访问一次的页面到达的。因此，我们在每次访问点击一次到达的页面时，继续枚举这个页面可以再点击一次到达的页面即可。int t[1010], a[1010][110], ans = 1; for (int i = 1; i <= t[1]; ++i) { ++ans; for (int j = 1; j <= t[a[1][i]]; ++j) ++ans; }有没有发现什么问题？在点击一次访问的页面中，可能有超链接是指向页面 $1$ 的，此时如果再访问这个页面，就会对页面 $1$ 重复统计。如何避免这样的问题呢？一个很直接的思路是：如果我们已经访问过某个页面，也就是说这个页面已经给答案加过 $1$ 了，那就跳过这个页面，不再统计。因此，我们需要新建一个 bool 数组，存储当前这个页面是否被访问过，被访问过为 true，否则为 false。假设这个数组为 $vis[]$（vis 即 visited，已访问过的缩写），那么 $vis[i]$ 表示这个页面的状态（即是否被访问过）。我们在每次访问到一个新页面时，判断当前页面的 $vis$，如果为 false，那么给答案加 $1$，然后给将这个页面的 $vis$ 修改为 true，表示已访问过。当然，页面 $1$ 无论如何都是会被访问的，因此还需要手动把 $vis[1]$ 设置为 true。此时，代码就呼之欲出了。int t[1010], a[1010][110], ans = 1; bool vis[1010]; vis[1] = true; for (int i = 1; i <= t[1]; ++i) { if (!vis[a[1][i]]) ++ans, vis[a[1][i]] = true; for (int j = 1; j <= t[a[1][i]]; ++j) if (!vis[a[a[1][i][j]]) ++ans, vis[a[a[1][i][j]] = true; }C 笨小猴 - 字符与 ASCII这题没上一道题那么抽象，应该不存在读不懂题的问题了吧。给定一个小写字母组成的字符串，求出现次数最多的字母的出现次数、 出现次数最少的字母的出现次数。作差，判断是否为质数。$50$ 分解法注意到，如果这个差值不是质数，那么输出的第一行总是 $\texttt{No Answer}$，第二行总是 $1$，直接骗分输出即可。正解很显然地，直接统计所有字符出现的次数即可，因此本题的瓶颈在于存储各个字符出现的次数。还记得我们之前学过的 char 的本质吗？ASCII 码，也就是整数，因此 char 变量可以直接作为数组下标使用。理解到这里后，统计字符的出现次数就变得十分简单了。假设我们使用 $cnt[]$ （cnt 即 count，数量的缩写）统计字符的出现数量，那么 $cnt[i]$ 可以表示 ASCII 码为 $i$ 的字符的出现次数。接下来考虑如何统计最大值和最小值。我们可以采用“打擂台”的想法：对于一个值，如果它比当前记录的最大值更大，那么就把最大值更新为当前这个值，最小值亦然。然而，可以发现，如果我们将最小值也初始化为 $0$ 的话，那么就没有比它更小的值了，也就无法更新得到答案了。因此，最小值应该初始化为一个极大值。我们还可以发现，ASCII 码表示的 $128$ 种字符中，只会出现 $26$ 种，如果我们统计到了那些没有出现的字符，最小值会更新为 $0$，也就无法继续更新答案了。因此，我们需要加一个特判，如果出现次数为 $0$，那么就不更新答案。加上我们之前讲过的质数判断即可。string s; int cnt[130], maxn, minn = 1e9; for (int i = 0; i < s.size(); ++i) ++cnt[s[i]]; for (int i = 0; i < 128; ++i) { if (cnt[i] > maxn) maxn = cnt[i]; if (cnt[i] && cnt[i] < minn) minn = cnt[i]; } if (maxn - minn < 2) return cout << "No Answer" << endl << 0 << endl, 0; for (int i = 2; i * i <= maxn - minn; ++i) if ((maxn - minn) % i == 0) return cout << "No Answer" << endl << 0 << endl, 0; cout << "Lucky Word" << endl << maxn - minn << endl;更优的正解我们只需要这 $26$ 种字符，那是不是意味着，只要排除掉其他字符的干扰，就可以省去更新最小值时候的特判呢？答案是肯定的。既然 char 本质上也是一种整数，它当然是可以进行运算的。我们知道，$26$ 个小写字母在 ASCII 码中是连续的，由 $a$ 到 $z$ 递增。因此，只需要在计算数组下标的时候，将原本的字符减去字符 ，即可获得范围在 $0$ 到 $25$ 之间的下标。例如，字符 $c$ 减去字符 $a$ 等于 $2$。这样的操作被称为映射。通过上述的映射操作，我们将 $0$ 到 $127$ 的范围压缩到了 $0$ 到 $25$，统计答案的数组可以开得更小，很大程度上减小了空间占用。另外，这里介绍两个新函数：max(a, b) 表示获取 $a$ 和 $b$ 中较大一个的值，min(a, b) 表示获取 $a$ 和 $b$ 中较小一个的值。我们每次获取最大值和某个字符出现次数之间较大的值，并将它重新赋值给最大值，即可完成更新操作；最小值亦然。代码如下。string s; int cnt[30], maxn, minn = 1e9; for (int i = 0; i < s.size(); ++i) ++cnt[s[i] - 'a']; for (int i = 0; i < 26; ++i) maxn = max(maxn, cnt[i]), minn = min(minn, cnt[i]); if (maxn - minn < 2) return cout << "No Answer" << endl << 0 << endl, 0; for (int i = 2; i * i <= maxn - minn; ++i) if ((maxn - minn) % i == 0) return cout << "No Answer" << endl << 0 << endl, 0; cout << "Lucky Word" << endl << maxn - minn << endl;