RyanLi 的博客 - 文档
type: channel
link: https://blog.ryanli.top/index.php/tag/%E6%96%87%E6%A1%A3/
items: 8. 高精度的基本运算
items: 9. 排序
items: 7. 函数
items: 4. for 循环与循环的应用
items: 5. 数组
items: 3. 复杂分支结构与 while 循环
items: 1. 顺序结构
items: 2. 简单分支结构

8. 高精度的基本运算
type: item
date: 2025-03-12T13:26:13+08:00
description: 在 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 的范围），…

9. 排序
type: item
date: 2025-03-12T13:26:00+08:00
description: 请注意，如无特殊说明，本文默认序列的下标从 $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$ …

7. 函数
type: item
date: 2024-02-02T20:36:00+08:00
description: 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; retur…

4. for 循环与循环的应用
type: item
date: 2024-02-02T20:34:00+08:00
description: 除了 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; }至此，我们已经学会了循环的全部内容。在今后的学习中，循环将是总会用到的知识点，希望各位能够熟练掌握。

5. 数组
type: item
date: 2024-02-02T20:34:00+08:00
description: 在学习了循环之后，我们来学习一个数据结构，当然，它很简单（）一维数组数组的创建我们先来看一个需求。如果你想要存储一些 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$ 行，每行…

3. 复杂分支结构与 while 循环
type: item
date: 2024-02-02T20:33:00+08:00
description: 嵌套我们已经学习完简单的分支结构，但是我们发现，生活中的事情并不是非黑即白的，只通过简单的 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 中非常重要的知识点，若不熟练掌握将…

1. 顺序结构
type: item
date: 2024-02-02T20:32:00+08:00
description: 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"; // 字符串，顾名思义，存储一串字符，使用双引号请牢记上述四种数据类型的使用方式及…

2. 简单分支结构
type: item
date: 2024-02-02T20:32:00+08:00
description: 逻辑表达式在计算机中真假是黑白分明的。计算机的世界由 $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;…