在 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。
Tips. 本文的所有代码请各位编译并运行后观察运行结果。无返回值函数的定义在之前的学习中，我们知道了 C++ 的程序入口是 main()，即主函数，那么我们除了 main() 函数外是否可以定义其他的函数呢？答案是肯定的。我们先来看一段定义函数的格式。返回值类型 函数名(参数类型1 参数1, 参数类型2 参数2, ...) { 函数体 }首先，我们介绍一下函数体。函数体是调用函数所执行的语句。注意，与我们之前讲过的 if 等不同，此处大括号不可以省略。返回值是调用函数后执行完所有语句返回的值（也可以理解为这整个函数代表的值的数据类型），如果没有返回值，必须要写 void（也就是英文中的空白）。参数是函数要进行操作的东西，可以在函数体中使用。我们先来看个例子：void print() { cout << "Hello, world!" << endl; }调用一次这个函数可以输出一次 Hello, world!。如果我们写一个这样的程序：#include <iostream> using namespace std; void print() { cout << "Hello, world!" << endl; } int main() { int n = 10; for (int i = 1; i <= n; ++i) print(); return 0; }请自行编译并运行这份代码，查看输出结果。可以发现，程序输出了 $10$ 行 $\texttt{Hello, world}!$。但是，如果我们想判断改变输出的字符串应该怎么办呢？我们重新定义 print 函数。#include <iostream> using namespace std; void print(string text) { cout << text << endl; } int main() { int n = 3; for (int i = 1; i <= n; ++i) print("Hello, world!"); for (int i = 1; i <= n; ++i) print("Fuck CCF."); return 0; }请同学们编译这段代码，查看输出结果。可以发现，程序输出了 $3$ 行 $\texttt{Hello, world!}$ 和 $3$ 行 $\texttt{Fuck CCF}$。这样一来，我们的函数通过传参（传递参数）就有了灵活性。一般函数的定义我们继续拓展深度。int add(int a, int b) { return a + b; }这个函数是一个具有 int 函数的返回值，它返回了 $a + b$ 的值。我们可以测试一下：#include <iostream> using namespace std; int add(int a, int b) { return a + b; } int main() { int a = 10, b = 20; cout << add(a, b) << endl; return 0; }得到了结果：30这样，我们的函数就不必更改函数的内容，而只更改参数就好了。观察下面这段代码，我们有这样一段函数：void add(int a, int k) { a += k; }我们知道 a += k 的含义，于是我们兴高采烈地运行这段代码：int main() { int a = 1; add(a, 1); cout << a << endl; }运行后得到了如下结果：1可以发现，函数并没有实现 a += 1 这一个操作。我们来究其根本。传参的一个重要特性是：大多数传参方式在对参数进行操作时，事实上，不会真正改变参数的值。但是有两种方式例外（其实还有一些没什么必要的方式，这里不再赘述）：传用数组。传引用类型的参数。我们说一下引用类型的参数的写法：void add(int &a, int k) { a += k; }我们将 add 函数换成这样的形式再运行一遍，得到如下结果：2结果和我们预想的相同了。函数的返回在循环中，我们知道我们可以使用 break 终止循环。如果我们想终止函数运行，应该怎么办呢？我们可以使用 return 来结束一个循环。void print(){ cout << "before" << endl; return; cout << "after" << endl; }运行后，我们发现，程序只输出了 before。在有返回值的函数中，也可以使用 return 语句中止函数，只需要在 return 后加上要返回的值即可：bool judge(int k) { for (int i = 1; i <= 10; ++i) if (i == k) return true; return false; }显然地，这个函数的作用是判断传入的 $k$ 是否在 $[1 , 10]$ 的范围内，如果是则返回 true，否则返回 false。变量的作用域$n$（$n \le 100$）名同学参加歌唱比赛，并接受 $m$（$m \le 20$）名评委的评分，评分范围是 $0 \sim 10$ 分。每名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 $m-2$ 个评分的平均数。求得分最高的同学分数是多少。本题的思路很简单，抽出每名同学得分中的最大、最小评分，去掉后求平均值，然后再取最大值。观察如下代码：#include <iostream> using namespace std; int s[25], n, m, maxsum; void stat(int a[], int m) { int maxscore = 0, minscore = 10, sum = 0; for (int i = 1; i <= m; ++i) { maxscore = max(maxscore, a[i]); minscore = min(minscore, a[i]); sum += a[i]; } maxsum = max(maxsum, sum - maxscore - minscore); // 计算评分总和，并更新最大值 } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) cin >> s[j]; stat(s, m); } cout << double(maxsum) / (m - 2) << endl; // 最后再计算平均值 return 0; }在这份代码中，我们使用了一个 stat() 函数处理一个给定的数组评分信息， 然后更新最高分的同学分数。本例的 stat() 函数中，接收的参数列表中的 int a[] 是指可以接收一个 int 类型的数组名。在函数中单个变量是可以传递实际参数的，但是传递数组名作为参数可不会把数组的所有信息当作实际参数传入函数，而只是传递数组在内存中的地址。就像在操作厨房自制机器时，可以把一个土豆、一个番茄放入机器中，但是如果有一排碗的食材，则只能告诉机器那一排碗的第一个碗在什么位置，让机器自己去指定位置找食材。因此在函数 stat() 中，数组 a[] 其实就是全局变量 s[] 的别名，如果在函数中改变 a[] 中的一项值，s[] 也会相应地改变。和全局变量对应的，在 stat() 函数中的变量 $m$、$maxscore$、$sum$ 等，都是在函数中定义的、在机器内部的变量，因此被称为局部变量。在函数中无论怎么改变这些局部变量，都不会影响到函数外面（函数里的 $m$ 变量和外面的 $m$ 没有关系了，也就是说函数外面的变量 $m$ 被屏蔽了）。也就是说，这些局部变量只能在这个函数中作用，因此这个函数是这些变量的作用域。类似地，我们常在 for 循环中定义的循环变量 $i$，它的作用域是整个循环，在循环之外无法调用这个变量。在程序设计竞赛中，建议大数组（超过 $1000$）作为全局变量定义。一是方便程序所有地方都可以访问到这个数组，二是有些评测环境栈空间（就是每个函数被分配到的内存空间）有限，可能会造成栈溢出。不过现在大多数比赛的评测环境下，栈空间可以达到要求的内存上限了。函数递归函数其实还可以调用它本身，也就是「递归」。值得注意的是，高中数学不区分递归和递推，但这在代码上有本质的区别，请注意区分。求 $n!$（$n \le 12$），也就是 $1 \times 2 \times 3 \times \cdots \times n$。请注意，你在本题中不被允许使用循环语句。计算阶乘很简单，但如果不允许使用循环语句，那么得想想别的办法。假设 $f(n)$ 代表 $n$ 的阶乘，那么阶乘还有另外一种表示方法：$f(1)=1$，$f(n) = n \times f(n-1)$。当想求 f(n) 时，就可以调用 f(n-1) 进而调用 f(n-2)……直到调用 f(1) 为止。像这样将规模大的问题转化成形式相同，但是规模更小的问题，就称为子问题。代码如下:#include <iostream> using namespace std; int n; int f(int n) { if (n == 1) return 1; // 如果 n 为 1，则返回 1 return n * f(n - 1); // 否则计算 (n - 1)!，并将其乘上 n 返回，得到 n! } int main() { cin >> n; cout << f(n) << endl; return 0; }一个函数不仅可以调用其他的函数，甚至还能调用自己，这种自己调用自己被称为递归。根据题意和上述思路，可以写出上面的递归做法。假设输入是 $3$，那么函数执行的步骤如下图所示：程序计算步骤如下：进入 main() 函数，收集到了参数 $3$，传递参数给 f() 函数，也就是调用 f(3)。进入第 $1$ 层 f() 函数，需要接收一个 int 类型的变量 $n$。传递进来了 $3$，所以这里的 $n=3$。现在需要知道 $f(3-1)$ 的值。因此传递参数 $2$ 给 f() 函数，调用 f(2)。进入第 $2$ 层 f() 函数（别忘了第一层 f() 函数还没结束，在等待答案呢），这里的 $n=2$。现在又要知道 f(2-1) 的值，因此再次传递参数 $1$ 给 f() 函数，调用 f(1)。进入第 $3$ 层 f() 函数。发现当 $n$ 等于 $1$ 时就返回 $1$，返回到第 $2$ 层 f() 函数，得到 f(2-1) 的值就是 $1$，继续进行运算。返回结果$2 \times 1=2$，返回到第 $1$ 层 f() 函数，得到 f(3-2) 的值就是 $2$，继续进行运算。返回结果 $3 \times 2=6$，返回到 main() 函数，得到 f(3) 的值是 $6$，输出这个结果。显然，虽然递归函数可以自己调用自己，但是不能无限制调用下去，所以必须要设置递归终止条件。上述代码的递归终止条件是 $f(1)=1$。递归函数有点类似于剥洋葱，一层套着一层，直到掰到最里层。读读下面的故事，或许可以进一步了解递归。从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：‘从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：‘太困了不讲了不讲了’，于是都回去睡觉了。”于是都回去睡觉了。’于是都回去睡觉了。”于是都回去睡觉了。这样的故事可以抽象成：void 讲故事() { if (困了) return; 讲故事; 回去睡觉; }函数几乎可以算是最难的基础内容，但是也是以后深入学习算法的必要条件，更是复杂算法的根本。请各位认真钻研，尽可能理解并掌握函数的用法。
除了 while 循环，C++ 还有两种循环结构。我们依次介绍一下。do while 循环在 C++ 中，还有一种循环叫做 do while 循环，这种循环和 while 循环差不多，我们先来看结构。do { 循环体 } while (条件);这种循环的流程是：先开始执行循环体，然后再进行 while 循环的条件判断，我们看看流程图。因此可以发现，无论条件如何，do while 循环总是会执行至少一次。for 循环我们先给出结构框架：for (初始化; 条件; 更新语句) { 循环体 }在这个框架中出现了几个新名词：初始化指定义循环的初始状态，也就是循环开始时是什么样的；更新语句是在每次循环后对状态进行更新，也就是执行完循环体后进行一些操作。观察下面一段代码：for (int i = 1; i <= n; ++i) cout << i << endl;这段代码中：int i = 1 是初始化，我们定义了一个变量 $i$，并赋了初值为 $1$。这个变量 $i$ 被称为循环变量，经常以 $i$、$j$、$k$ 等命名。在 for 循环中定义的循环变量只有在这个循环内部（包括初始化、条件、更新语句和循环体）才可以使用。i <= n 是条件，这与我们在 while 循环中学到的相同。++i 是更新语句，在每次循环结束以后会执行一次。这段代码的意思是，让 $i$ 开始为 $1$。若 $i \le n$，则执行 cout << i << endl，也就是输出 $i$，否则结束循环。每一次执行完循环体后，$i$ 变为 $i+1$。这是 for 循环的流程图：如果把上面的代码改成 while 循环，应该怎么写呢？int i = 1; while (i <= n) { cout << i << endl; ++i; }此时我们可以发现，for 循环和 while 循环是可以相互转化的（当然 do while 循环也同理），并且在大多数时候 for 循环要比 while 循环轻量，简便。值得注意的是，for 循环的初始化、条件、更新语句都不是必要的，甚至只写两个分号也可以构成 for 循环。循环操作我们通常可以对循环做两种操作：退出循环、跳过循环体的余下部分。break 的作用是跳出一层循环，而 continue 的作用就是跳过本次循环中未执行的语句，直接进入下一轮循环。使用这两个语句可以使循环（或循环体）提前结束，且只能控制这两种语句上一层循环的流程。break 与 continue 语句均可在三种循环语句的循环体中使用。举个例子，观察下面的几段代码：for (int i = 1; i <= 10; ++i) { cout << i << ' '; }for (int i = 1; i <= 10; ++i) { if (i == 6) break; cout << i << ' '; }for (int i = 1; i <= 10; ++i) { if (i == 6) continue; cout << i << ' '; }这几段代码中：第一份代码可以直接输出从 $1$ 到 $10$ 的所有数。第二份代码中，我们使 $i$ 等于 $6$ 的时候退出循环，因此不会继续输出；第三份代码中，我们使 $i$ 等于 $6$ 的时候跳过这次循环的剩余部分，然后进入下一次循环，因此只有 $6$ 不会被输出。它们的运行结果是这样的：1 2 3 4 5 6 7 8 9 101 2 3 4 51 2 3 4 5 7 8 9 10这时我们可以想到，如果判断不满足条件时直接使用 break 跳出循环，是等价于写一个循环条件的，这也就是上文所说「循环条件可以省略」的原因。循环的应用我们来看几道深度应用循环的题目：给定一个数 $x$，请判断他是否是质数。我们知道，对于一个质数，它只有 $1$ 和它本身两个因数，所以我们枚举所有在 $[2,x-1]$ 的数 $d$，判断 $d|x$ （即 $x$ 能被 $d$ 整除）是否成立即可。输出一个数所有的倍数。我们只需要将 $i$ 初始设为 $x$，每次循环结束让 $i$ 变为 $i+x$ 即可。输出一个数 $x$ 中数字 7 的个数。我们先将数转化为数字，然后统计即可。于是考虑如何将数转化为数字。在十进制下，每个数的最后一位是 $x\bmod 10$。于是我们就可以写出这样的代码：while (x != 0) { if (x % 10 == 7) ++ans; x /= 10; }至此，我们已经学会了循环的全部内容。在今后的学习中，循环将是总会用到的知识点，希望各位能够熟练掌握。
在学习了循环之后，我们来学习一个数据结构，当然，它很简单（）一维数组数组的创建我们先来看一个需求。如果你想要存储一些 int 变量，你会怎么做？如果个数少的话，我们可以选择 int a, b, ...;。但是如果变量很多（比如有 $10^5$ 个），这样定义是永无止境的，所以我们应该如何解决呢？于是，我们引入一种数据类型——数组。int a[114514];我们使用中括号 [ ] 来定义一个数组。其中，int 代表这个数组中存储的变量类型为整数，$a$ 是数组的名字，$114514$ 是数组的大小（也就是里边包含多少个变量，我们将数组里的变量称为元素）。类似地，如果我们想要大量存储其他类型的变量，也可以使用数组。例如，我们可以使用 double b[10]; 创建一个大小为 $10$ 的浮点数数组 $b$。如果我们想要获取数组中的元素，我们同样使用中括号 [ ]，使用 varname[index]。其中，varname 是数组的名称，index 是这个元素在数组中的位置（也就是数组的第几个元素），被称为下标。这样获取数组中元素的行为被称为访问。值得注意的是，数组的下标从 $0$ 开始，也就是说，一个大小为 $N$ 的数组的下标为 $0\sim N-1$。当我们访问的位置超出这个范围时（比如访问负数或者 $\ge N$ 的下标），就会出现一些奇奇怪怪的错误，这样的行为被称为数组越界。在 OI 中，为了方便，我们一般会将数组的大小开的比数据范围略大一些，舍弃下标为 $0$ 的位置。数组的初始化虽然我们已经创建了一个数组，但是如果数组是在函数（比如主函数）中创建的，直接访问这个数组将会得到一些奇奇怪怪的结果，比如：int a[5]; for (int i = 0; i < 5; ++i) cout << a[i] << endl;一种可能得到的结果如下：4283280 1 1876947504 1 -2113433532可以发现，这似乎与我们的预期相差甚远。这是因为，当我们访问一个未初始化的数组时，计算机并不知道我们要访问的元素的值时多少，于是就可能会随机给出一个值。对于上述操作，甚至在不同的时间或不同的电脑上得到的结果也可能不相同。这样不知道会有什么结果的行为被称为未定义行为，也常简写为 UB（Undefined Behavior），比如把答题卡的定位点之间的空隙全都涂黑就是一种 UB。我们要在代码中尽可能避免 UB，以避免出现各种奇奇怪怪的错误。此时，我们就需要对这个数组进行初始化，也就是给它赋一个初值。我们可以在创建数组时，将我们要初始化的值放在大括号 { } 内，并将其赋值给数组来进行初始化。例如：int a[5] = {0}; for (int i = 1; i < 5; ++i) cout << a[i] << endl;0 0 0 0 0可以发现，此时数组的每个元素就都有了初值。那么如果我们在大括号里写 $1$，数组会被全部初始化为 $1$ 吗？答案是否定的。这样做只会给数组最开头的元素初始化为 $1$，而其他元素仍然为 $0$。也就是说，大括号中可以初始化的是数组的前几个值，剩下的会初始化为 $0$。例如下面这段代码和输出：int a[5] = {114, 514, 1919810}; for (int i = 1; i < 5; ++i) cout << a[i] << endl;114 514 1919810 0 0当然，初始化的过程中，同样要避免数组越界。数组的应用我们来看一个实例：向数组 $a$ 中输入 $n$ 个整数，$n \le 10^5$。由于 $n$ 很大，我们很难将 $n$ 个数字一个个手动输入，但可以发现的事，程序是在做同样的事情——「输入」。这个时候，就要联系到前几周学过的循环结构上来了，使用循环输入即可很好的解决这一问题。int a[100010]; // 稍微开大一点，防止越界 for (int i = 1; i <= n; ++i) cin >> a[i];求数组中的 $n$ 个元素的和。int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i];多维数组如果我们想存储一个矩阵，又该如何操作呢？于是我们引入了二维数组。typename varname[N][M];typename 指数组的数据类型。这段代码表示我们创建了一个 $N\times M$ 的二维数组，也就存储了 $N \times M$ 个整数。二维数组的本质是将一个数组的下标指向另一个数组，也就是「数组的数组」。类比一维数组，当我们想访问第 $x$ 行第 $y$ 列的数，可以使用 varname[x][y] 进行操作。以此拓展，还可以有三维数组、四维数组……给出 $n$ 行，每行 $m$ 个整数，向二维数组中输入。值得注意的是，尽管我们学过循环，但只写一层循环，或是只有一个循环变量，似乎怎么也实现不了。这个时候，我们就需要使用循环嵌套了。我们将两层循环嵌套在一起，外层循环用于读入一整行的内容，一共执行 $n$ 次，内层循环用于读入每行的每一个元素，一共执行 $m$ 次。代码如下：for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j];当然，循环也是可以无限嵌套的，因此，更高维度的数组也可以类比上述操作。数据范围与空间不知道各位在做题的时候是否注意到，每道题都有一个的时间限制与空间限制，当然，并不知道这是什么意思。计算机的存储单位从学过数组开始，我们经常需要存储大量的数据。然而，计算机存储数据也是需要花费代价的，也就是占用存储空间。此时，题目给出的空间限制就变成了我们需要考虑的东西——我们需要保证存储的这些数据不超过空间限制。具体地说，计算机存储的最小单位是位（bit, b），一位只可以表示 $0$ 和 $1$ 两个值，也就构成了一个二进制位。每 $8$ 位就可以构成一个字节（Byte, B），接下来以 $1024$（也就是 $2^{10}$）为进制，依次有千字节（Kibibyte, KiB）、兆字节（Mebibyte, MiB）、吉字节（Gibibyte, GiB）等等。也就是说，它们之间有如下的关系：1B = 8b，1KiB = 1024B，1 MiB = 1024KiB，1GiB = 1024MiB……值得注意的是，我们平时经常看到 KB、MB、GB 等写法，在大多数时候它们指的就是我们刚才提到的 KiB、MiB、GiB 等，但事实上这是一套以 $1000$ 为进制的存储单位，这两种写法完全是两种体系，请各位不要混淆。数据类型的空间与范围了解计算机存储的计算方式后，接下来我们给出常用的一些数据类型的占用空间。除去我们之前介绍的几种，还会介绍更多的数据类型，方便解决更多题目。数据类型范围近似范围空间布尔 bool$[0, 1]$$[0, 1]$1B字符 char$[-2^7, 2^7 - 1]$$[-128, 127]$1B整数 int$[-2^{31}, 2^{31} - 1]$$[-2 \times 10^9, 2 \times 10^9]$4B无符号整数 unsigned int$[0, 2^{32} - 1]$$[0, 4 \times 10^9]$4B64 位整数 long long$[-2^{63}, 2^{63} - 1]$$[-9 \times 10^{18}, 9 \times 10^{18}]$8B无符号 64 位整数 unsigned long long$[0, 2^{64} - 1]$$[0, 1.8 \times 10^{19}]$8B双精度浮点数 double$[-1.8 \times 10^{308}, 1.8 \times 10^{308}]$，精度 $15 \sim 16$ 位 8B扩展精度浮点数 long double$[-1.2 \times 10^{4932}, 1.2 \times 10^{4932}]$，精度 $18 \sim 19$ 位 16B另外，除了空间，每种数据类型可以表示的数据的范围也都不一样，我们也给出了常用数据类型的范围，今后做题就需要同时考虑数据范围和空间限制了。数组是我们接触的第一个数据结构，也是之后学习绝大多数数据结构的基础，请各位熟练掌握，并着重理解与循环的关系。
嵌套我们已经学习完简单的分支结构，但是我们发现，生活中的事情并不是非黑即白的，只通过简单的 if 与 else 似乎无法完成复杂的条件判断。接下来我们将学习如何实现这些较为复杂的条件判断。洛谷 P5714。本题需要计算 BMI 指数，直接按照给出的公式计算即可，关键是如何根据不同的区间来分类。我们仍然可以使用 if 语句。注意到，这里需要针对三个情况进行判断，而非两种情况。因此，我们引出 else if 结构。通过 else if 可以同时对多个条件进行判断，组成更复杂的条件分支，基本结构如下：if (条件 1) { 条件 1 成立时执行语句; } else if (条件 2) { 条件 2 成立时执行语句; } ... else { 条件 1 与条件 2 均不成立时执行语句; }值得注意的是，else if 可以写无限多个（即上面代码中省略号的含义），也就是说，有了 else if，我们就可以同时判断许多并列的条件了。于是上面的问题就可以写出代码了：#include <iostream> using namespace std; int main() { double m, h, BMI; cin >> m >> h; BMI = m / h / h; if (BMI < 18.5) cout << "Underweight" << endl; else if (BMI < 24) cout << "Normal" << endl; else { cout << BMI << endl << "Overweight" <<endl; } return 0; }现在我们还想知道，对于 BMI 低于 $18.5$ 的同学，他的身高 $h$ 是否超过 $1.6$ 米，如果是则输出 $\texttt{Tall}$，否则输出 $\texttt{Short}$。对于这个问题，我们需要先判断 BMI 是否符合条件，再判断身高，这并非我们刚才提到的并列关系。此时与使用 else if 的情况又不同了。可以发现，上文提到的 else if 实际上是判断 else 以后进入了一个新的 if，所以当我们为它加上大括号，这一处分支的结构就变成了这样。if (条件 1) { 条件 1 成立时执行语句; } else { if (条件 2) { 条件 2 成立时执行语句; } }这样在 if 或 else 中套了一个新的 if 或 else 的行为被称为嵌套。当然，我们仍然可以在嵌套中继续添加嵌套。对于上面的问题，我们使用嵌套的分支结构，首先判断 BMI 是否低于 $18.5$，然后再判断身高即可。if (BMI < 18.5) { cout << "Underweight" << endl; if (h > 1.6) cout << "Tall" << endl; else cout << "Short" << endl; }while 循环洛谷 P5720。可以发现，我们前面学过的顺序结构与分支结构都无法解决这道题（除非写好几十个 if）。这时应该怎么办呢？很好想，解决这道题的中心思想，其实就是一直给这个数除以 $2$。这里的「一直」，就是这道题的关键。当我们想要重复执行某个语句时，就需要用到循环结构。循环，顾名思义，它可以反复执行同样的语句，这样就可以大大减少代码的长度。以下是循环结构的流程图：我们先来介绍第一种循环：while 循环。while 循环的结构为：while (循环条件) { 循环体 }与我们之前学过的 if 相同，while 循环同样是在小括号 ( ) 里写下循环需要进行的条件，C++ 将会在每次循环开始时判断条件是否成立；在大括号 { } 里写下条件成立时需要执行的代码块，这个代码块被称为循环体。当然，如果循环体只有一个语句，这里的大括号同样可以省略。注意到，小括号里只有循环成立的条件，而没有指定循环的次数，是通过条件是否成立判断循环是否继续的。因此，while 循环常用于不知道循环次数的循环。题目中让我们求「第几天的时候木棍长度变为 $1$」，这就告诉我们循环的条件是「木棍长度大于 $1$」（或是「木棍长度不等于 $1$」）。我们在每一轮循环都对木棍的长度除以 $2$，并且给天数加上 $1$ 即可。代码如下：while (a > 1) { a /= 2; // 等价于 a = a / 2; ++ans; // 等价于 ans++; 或 ans += 1; 或 ans = ans + 1; }在上面的代码中，我们使用 $a$ 存储木棍的长度，使用 $ans$ 存储答案（即天数）。从现在开始，为了提升同学们独立编写代码的能力，我们将只给出核心代码，剩下的部分请自主完成。分支结构与循环结构是 OI 中非常重要的知识点，若不熟练掌握将寸步难行，请各位尽力学习并理解循环结构。
C++ 基本结构观察下面一段代码：#include <iostream> using namespace std; int main() { cout << "Hello world!"; return 0; }此时运行这一段代码，即可看到控制台上的输出内容。Hello world!这个程序的目的很简单，就是在屏幕上显示（C++ 中我们称之为输出）一句话： Hello world!。当你成功输出这段文字，意味着你打开了编程世界的大门，你成功向这个新世界打了个招呼！下面来逐句分解这个程序。头文件#include <iostream> 是头文件，用于引入外部库。举个例子，想要烹饪一道菜，除了食材之外还需要一些其他工具，如锅和铲子。在英语中，input 代表输入，output 代表输出，stream 代表流——C++ 的一种操作方式。取 input 和 output 的首字母，和 stream 拼起来，这个程序使用的 iostream 头文件是一个可以用来输入输出的“工具”。之后会接触更多的头文件，甚至可以自行编写头文件，也就是造一个工具。命名空间using namespace std; 是命名空间声明语句。暂时不用理解它的用途，并且你在相当长的一段时间内也不需要理解它，只需要记住在头文件之后加上这句话即可。主函数int main() 是主函数，这样带小括号的语句被称为函数。可以看到主函数后面有一对大括号 { }，将主函数中的语句给包围起来了。计算机运行程序的时候，会从 int main() 后面的大括号开始运行，依次执行大括号中的语句直到结束。举个例子，仍旧是想要烹饪一道菜，那么“炒菜”这个动作就是主函数。炒菜这个主函数里还包含别的步骤，例如“洗菜”“切菜” “下锅翻炒”“调味”“起锅装盘”就是这个主函数里面的语句。输出cout << "Hello world!"; 是输出语句，该语句可以让计算机输出一句话（注意是两个英文的小于号，而不是中文的左书名号）。我们将在下面的「输入与输出」部分详细讲解。返回值return 0; 的意思是，主函数在结束时需要告诉系统一个数字 $0$，这样「告诉」的操作在 C++ 中被称为返回，返回的东西被称为返回值。当主函数的返回值为 $0$ 时，这说明程序正常运行结束。在主函数中即使不写这一句话，编译器也会在编译时自动加上这句话。值得注意注意，千万不要返回一个其他的非 $0$ 值，这会造成系统认为这个程序异常退出。在算法竞赛中，这会导致被认为运行时错误。暂时不用理解它的用途，但是并且你在相当长的一段时间内也不需要理解它，只需要记住在主函数末尾加上这句话即可。变量很显然，C++ 能够完成的任务远不止计算一些东西这么简单，有的问题是需要进行很多计算才能解决的。因此，我们需要有一个办法能够储存计算的中间结果。这时，可以使用变量来满足这个要求。这时变量的用途也就显而易见了：存储信息。观察下面一段代码：#include <iostream> using namespace std; int main() { int a = 1, b; b = 2; int c = a + b; cout << c; return 0; }不难想出，这个程序的运行结果应该如下：3变量的定义注意到，在代码的第 4 行，出现了一个我们从来没有见过的语句：int a = 1, b;。可以想到，英语中有一个 integer 的单词，意为「整数」。事实上，这里的 int 就取了前三个字母，表示这是一个整数变量，这个 int 被称为数据类型。$a$ 和 $b$ 是两个不同的变量名，因此可以发现，多个变量之间可以使用逗号隔开。此时，我们就已经创建了名为 $a$ 和 $b$ 的两个整数变量，这个创建变量的过程被称为定义。但是还有一个 a = 1 的部分没有解决。变量是用来存储信息的，但我们使用定义变量 $a$ 的时候还并没有让它存储什么东西。这里的等于号与数学上的等于不完全相同，它的意义是赋值，也就是让等于号前面的变量存储等于号后面的东西。此时，变量 $a$ 已经存储了整数 $1$。然而变量 $b$ 还没有存储任何信息。注意到代码第 $5$ 行，出现了单独的 b = 2; 的语句。没错，赋值操作不一定要在定义变量的时候可以进行。事实上，赋值可以在代码的任何地方进行。上面只讲了整数，C++ 可以存储其他信息吗？答案是肯定的。下面给出了另外一些你目前可能用到的数据类型。double a = 1.14514; // 实数，可以为小数或整数（我们把这样的数据类型称为浮点数） char b = 'a'; // 字符，存储的信息使用单引号 string c = "abcd"; // 字符串，顾名思义，存储一串字符，使用双引号请牢记上述四种数据类型的使用方式及用途，我们将在接下来经常用到。数学运算类比数学，C++ 也可以进行数学运算。加号 + 和减号 - 在键盘上可以直接打出来，因此 C++ 的加号也是 +，减号也是 - 。由于我们无法在键盘上打出数学上的乘除号，因此我们引入新的符号。在 C++ 中，乘号写作 *，除号写作 /（请注意斜杠的方向）。观察下面一段代码（如果无法理解输出部分，请先阅读下面的「输入与输出」部分）：#include <iostream> using namespace std; int main() { int a = 1, b = 2, c = 3; cout << a + b << ' ' << a - b << ' ' << b * c << ' ' << c / b; return 0; }运行程序，得到了下面的运行结果：3 -1 6 1可以发现，前面三个都是我们想要的结果，但是对于第四个结果，为什么 $c \div b = 1$ 呢？整除运算还记得我们上面说的，int 代表的是整数类型。C++ 其实是一个很傻的东西，它不知道两个整数相除为什么会得到一个浮点数，它只知道 $3$ 里边有 $1$ 个 $2$，所以 c / b 这个表达式的结果是 $1$。这就是 C++ 在进行整数除法时进行的取整方式：向 $0$ 取整。为什么不是向下取整呢？通过实践可以得到，当结果为负数时，它又变成了向上取整。具体的原理我们现在无需理解，只需要记住整除会向 $0$ 取整即可。问题又来了，如果我想得到一个浮点数的结果应该怎么做呢？很简单，既然 C++ 不会两个整数相除得到浮点数，那我们让其中一个整数以浮点数的形式出现不就好了吗？观察下面这段代码：#include <iostream> using namespace std; int main() { int b = 2; double c = 3; cout << c / b; return 0; }得到了以下结果：1.5这与我们的预期相符。当然，$b$ 为 double $c$ 为 int ，或 $b$、$c$ 都为 double 时同理。取模运算不难想到，进行整除运算以后，很多时候都会剩下余数。当我们想要求这个余数的时候怎么办呢？一个一个减似乎有点太慢了，这个时候我们引入一个新的运算：取模，它的符号是 %，在数学上写作 $\mod{}$，原本在除法式子里的除数，在取模运算里被称为模数。观察下面这段代码：#include <iostream> using namespace std; int main() { int a = 10, b = 3; cout << a % b; return 0; }得到以下结果：1这与我们的预期相符。值得注意的是，由于涉及分数的除法没有余数的相关概念，因此取模运算也只能由整数参与运算。运算优先级C++ 中的运算优先级与数学上相似：先算乘 *、除 / 和取模 %，再算加 + 减 -。如果需要先计算某一部分，我们可以在需要先算的这一部分两端加上小括号 ( )。如下面这一段程序：#include <iostream> using namespace std; int main() { int a = 3, b = 4, c = 5; cout << (a + b) % a * c + b; return 0; }得到了以下的结果：9在这里，被小括号括起来的 $a+b$ 先进行了运算，然后再对 $a + b$ 进行后面的取模和乘法运算，最后再加上 $b$，得到结果 $9$。输入与输出输入因为我们正在学习的语言叫做 C++，输入的英文为 input，因此，C++ 中的输入语句是 cin（当然 cin 的实际含义并不是这样，但你可以在很长一段时间内都这么理解，方便记忆）。假如这里有一个变量 $a$，那么我们可以使用 cin >> a; 进行输入，也就是把外部的东西存储到变量 $a$ 中。这里的 >> 被称作输入流运算符，不过名字不重要，我们可以把它当作一个箭头理解。当输入的时候，信息从外部存储到变量内部，因此这个箭头指向变量。当然，cin 是忽略空格和换行的，这也就意味着我们可以连续使用 cin。假如这里有 $3$ 个变量 $a$，$b$ 和 $c$，我们就可以使用 cin >> a >> b >> c; 一次性读入这三个变量。输出类比输入，C++ 的输出语句是 cout。对于我们上面提到的所有数据类型，我们都可以使用 cout 进行输出。cout 后面既可以跟一个实际的值，也可以跟一个变量。假如这里有一个变量 $a$，那么我们可以使用 cout << a; 进行输入，也就是把变量 $a$ 中的信息输出出来。这里的 << 被称作输出流运算符。当输出的时候，要把变量中的信息传递到外部，所以这个箭头从变量发出，指向 cout，也就是外部。从这里我们可以发现，被称作流运算符的「箭头」，总是指向信息传递的方向。与 cin 相同，我们也可以连续使用 cout。假如这里有 $3$ 个变量 $a$，$b$ 和 $c$，我们就可以使用 cin >> a >> b >> c; 一次性读入这三个变量。我们可以使用 endl 输出换行，用法将在下面的代码中给出。有了输入，我们就可以进行交互式操作了，也就是对每次给出的数据进行运算，而不是针对一个程序里定死的值进行结果不变的运算。观察下面一段代码：#include <iostream> using namespace std; int main() { int r; cin >> r; cout << 3.14 * r * r << endl; return 0; }我们输入了一个整数变量 $r$，并且输出了 $3.14 \times r \times r$。发现这是一个输入半径，求圆的近似面积的问题。由于输入会有变化，所以对于不同的输入，输出也会有变化。至此，你已经学会了信息学竞赛中最为基础也最为重要的内容，这将是我们接下来学习一切知识点的基础，请务必熟练掌握。
逻辑表达式在计算机中真假是黑白分明的。计算机的世界由 $0$ 和 $1$ 组成，$0$ 代表假，$1$ 代表真。我们输入两个整数 $a$ 和 $b$，现在你需要判断 $a$ 是否大于 $b$、$a$ 是否小于或等于 $b$、$a$ 是否不等于 $b$。输出 $3$ 个整数，用空格隔开。对于每个询问，如果成立则输出 $1$，否则输出 $0$。#include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << (a > b) << ' ' << (a <= b) << ' ' << (a != b); return 0; }可以发现，> 是大于，<= 是小于或等于，!= 是不等于。注意，如果要比较两个数是否相等， 使用的是 == 而不是 =，因为一个等号是赋值的意思。由这些关系运算符组成的不是 $0$ 就是 $1$ 的表达式被称为关系表达式。我们用 $1$ 来代表真（成立），用 $0$ 来代表假（不成立）。在关系运算符左右两边放表达式（数字或者变量等），就会计算这两边的关系，返回 $1$ 或者 $0$。需要注意的是，如果关系表达式和算数表达式符号(如 +、-、*、/、%)一起使用，需要注意优先级问题。我们将在下文统一整理绝大多数各位目前可能用到的运算符的优先级。现在提出上面问题的升级版：请你判断 $a$ 是否大于等于 $b$ 并且 $a$ 不等于 $0$，$a$ 是否小于 $b$ 或者 $b$ 是否等于 $1$（注意这一共十两个问题）。输出 $2$ 个整数，用空格隔开。注意到，现在有「并且」和「或者」这两个我们无法处理的关系。此时需要引入逻辑运算符。我们令 && 表示「并且」，|| 表示「或者」，注意这里是两个同样的 & 和 |，单个的尽管在一些时候也可以运行，但它表示的含义完全不同，我们将在后面「位运算」一章讲到。这样一来，上面的问题也可以被解决了。#include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << (a >= b && a != 0) << ' ' << (a < b || b == 1) << endl; return 0; }如果此时向程序输入 2 2，那么获得的输出将是 1 0，因为 $a \ge b$，$a \not< b$ 而且 $b \ne 1$。接下来从优先级高到低整理了常用运算符的优先级，高优先级先进行运算，相同优先级从左到右按顺序运算，请务必熟悉。-（负号）*、/、%+、-（加减运算）<、>、<=、>===、!=&&` `分支语句if洛谷 P5712。对于这道题目，要写出一个正确的英语句子。根据输入数据不同程序要做出不同的表现——如果输入不是 $0$ 或 $1$，就多输出一个 $\texttt{s}$。代码如下：#include <iostream> using namespace std; int main() { int x; cin >> x; cout << "Today, I ate " << x << " apple"; if (x != 0 && x != 1) { cout << "s"; } cout << "." << endl; return 0; }在这个程序里，出现了一个我们从未见过的语句—— if。一般地，if 有如下格式：if (成立条件的表达式) { 当条件成立时需要执行的语句; }这里的「成立条件表达式」一般是指上面介绍过的关系表达式或者逻辑表达式——如果表达式是 $1$，或者只要不是 $0$，条件都会成立；如果是 $0$，条件就不成立了。正如其在英文中的意思一样，if 表示「如果」。如果括号中的条件成立，程序将执行大括号 { } 中的内容；如果不成立则不执行。因此，上面代码的流程是这样的：首先输入 $x$ ，知道吃了几个苹果。然后输出 $\texttt{Today, I ate } x \texttt{ apple}$，因为无论 $x$ 是多少，都要输出这样的句子。然后，当 $x$ 既不是 $0$，也不是 $1$ 时，说明要加上表示复数的 $\texttt{s}$。这就是 if 语句的作用。else洛谷 P5713。分析题目后可以发现，我们可以很容易地列出两种方式下分别消耗的时间——本地上传需要花费 $5n$ 分钟的时间， 而上传洛谷需要花费 $11+3n$ 分钟时间。如果前者小于后者，则选择在本地配置，否则选择洛谷上传。代码如下：#include <iostream> using namespace std; int main() { int n; cin >> n; if (5 * n < 11 + 3 * n) { cout << "Local" << endl; } else { cout << "Luogu" << endl; } return 0; }注意到，这份代码中又多出来了一个 else 语句。如果有 else，前面一定有至少一个 if 。用法如下：if (成立条件的表达式) { 当条件成立时需要执行的语句; } else { 当条件不成立时需要执行的语句; }正如 else 其意「否则」。这里是 if 语句的另外一种用法，配合上 else，就可以在条件成立的情况下做什么事情，否则，当条件不成立时做另外的一些事情。这里给出上面代码的流程图：st=>start: 输入 n cond=>condition: 本地时间更少？ op1=>operation: 输出 ”Local“ op2=>operation: 输出 “Luogu" e=>end: 结束 st->cond cond(yes)->op1->e cond(no)->op2->e特别地，如果需要执行的只有一条语句（也就是只有结尾的一个分号），那么大括号可以不要（甚至换行也可以不要），而空格和换行也都不是 C++ 的硬性要求。甚至，判断语句也可以不换行，上面的代码哪怕写成 if (5 * n < 11 + 3 * n) cout << "Local" << endl; else cout << "Luogu" << endl; 也是可以被运行的。但如果取消所有空格和换行，代码的可读性将会大幅降低，我们不推荐取消许多换行与空格。缩进与代码块在接触 if 语句时，写出来的代码开始有了「层次感」——上面代码中 if 语句后大括号内的语句相比于其他语句要往右移动了一点，这就是缩进。我们通常使用 $4$ 个空格作为每个层级的缩进，这样可以一目了然地知道哪些语句是条件成立时才执行的。使用大括号 { } 括起来的语句称为代码块，代码块里面的代码相比于外面应当有统一的缩进。开头大括号可以像例子中给出的那样不换行，也可以另起一行，这取决于个人习惯。总之，写程序应当有良好的代码规范，比如换行、空格、缩进等，这也是为了使代码可读性强，更容易理解。至此，你已经可以完成简单的条件判断了，这在以后将是相当常用的，请多加练习并尽量熟练。