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;
A 魔方 - 顺序结构求一个 $n$ 阶魔方的角块，棱块，中心块的数量。角块永远为 $8$ 个，直接输出即可。棱块为 $12 \times (n - 2)$ 个，输出这个式子的结果即可。中心块为 $6 \times (n - 2)^2$ 个。注意到，这个式子里出现了乘方，然而我们并没有学过乘方如何计算。考虑二次方的本质，其实是两个 $(n - 2)$ 相乘，因此输出 $6 \times (n - 2) \times (n - 2)$ 的结果即可。值得注意的是，如果你使用 pow 函数，输出时需要转换为整数类型，否则在面临较大数据时会以科学计数法的形式输出。#include <iostream> using namespace std; int n; int main() { cin >> n; cout << "8 " << 12 * (n - 2) << ' ' << 6 * (n - 2) * (n - 2) << endl; return 0; }B 学校 - 分支结构三栋楼图书馆、综合楼、艺术楼的楼层分别为 $3,5,9$，人流量分别为 $a,b,c$。已知目标教室的楼层 $n$，并且所在教学楼是可能的教学楼当中人流量最小的一栋，输出其名字。本题要依次判断两个条件，第一个是楼层限制，第二个是人流量。只需按照题意依次判断即可：如果 $n \le 3$，则三栋楼都需要考虑，就应该从 $a,b,c$ 三个中判断出最少的，输出对应的名字。如果 $3 < n \le 5$，则只可能在综合楼和艺术楼里，就应该从 $b,c$ 两个中判断哪一个较少，输出对应的名字。如果 $5 < n \le 9$，则只可能在艺术楼里，直接输出其名字即可。此外，输出时，如果担心出现偏差，可以直接复制题目给出的字符串。#include <iostream> using namespace std; int n, a, b, c; int main() { cin >> n >> a >> b >> c; // cin 会忽略空格和换行，一次性输入即可 if (n <= 3) { if (a < b && a < c) cout << "library" << endl; else if (b < a && b < c) cout << "comprehensive" << endl; else cout << "art" << endl; } else if (n > 3 && n <= 5) { // 只考虑 b, c 即可 if (b < c) cout << "comprehensive" << endl; else cout << "art" << endl; } else cout << "art" << endl; // 大于 5 则直接输出 art 即可 return 0; }C 教室 - 循环结构与简单数学推导有 $n$ 个柜子，第 $i$ 个柜子有 $a_i \times b_i$ 个格子，每个格子由 $c_i$ 个学生使用。因此得到学生总数与桌子总数，按照指定列数来摆桌子，尽量摆成整齐的矩形，多余的放到最后一排的后方，求最后的排数和最后一排桌子的张数。本题一共分两个部分，第一个部分是求出桌子总数，第二个部分是求出摆好之后桌子的排数和最后一排的桌子数量。对于第一部分，显然，对于第 $i$ 个柜子，应该有 $a_i \times b_i \times c_i$ 个学生使用，将所有的柜子对应的学生个数累加就得到了学生总数，等于桌子总数。接着就是第二部分。不难发现，桌子的排数应该是总数除以列数并向上取整。因为如果恰好整除，则排数等于总数除以列数，否则，等于其加一。这里给出一个结论，$\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor$，$a,b$ 为整数且 $b > 0$，请各位自行证明（$\lceil \ \rceil$ 代表向上取整，$\lfloor \ \rfloor$ 代表向下取整，这与我们数学教材上的取整符号有所不同，请注意区分）。这个结论可以帮助我们简化代码，无需额外写一个判断语句，简洁清晰。然后，我们假设学生总数为 $sum$，那么对于最后一排的桌子数量，显然就等于 $sum \bmod m$ 了。值得注意的是，当能够整除时，桌子摆成了矩形，最后一排的桌子数量等于 $m$，但此时 $sum \bmod m = 0$，所以要特判（就是判断特殊情况）。#include <iostream> using namespace std; int n, m, a, b, c, sum; int main() { cin >> n >> m; while (n--) cin >> a >> b >> c, sum += a * b * c; // 使用逗号可将多个语句合并为一句 cout << (sum + m - 1) / m << ' '; // 排数等于总人数除以列数的向上取整 if (sum % m == 0) cout << m << endl; // 如果正好可以排成一个矩形，则最后一排的人数等于列数 else cout << sum % m << endl; // 否则输出最后一排的人数 return 0; }对于上面的代码，出现了 while (n--) 这样的语句，它在这里等价于：while (n > 0) { // 循环体 n--; }因为 n-- 等价于 n = n - 1，也就是每次给 $n$ 减去 $1$，所以 $n$ 在不等于 $0$ 的时候，循环条件是成立的，当 $n$ 为 $0$ 时（也就是循环条件的值为 $0$），循环结束。另外，上面的 while 循环也可以改成 for 循环：for (int i = 1; i <= n; ++i) cin >> a >> b >> c, sum += a * b * c;
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$ 个空格作为每个层级的缩进，这样可以一目了然地知道哪些语句是条件成立时才执行的。使用大括号 { } 括起来的语句称为代码块，代码块里面的代码相比于外面应当有统一的缩进。开头大括号可以像例子中给出的那样不换行，也可以另起一行，这取决于个人习惯。总之，写程序应当有良好的代码规范，比如换行、空格、缩进等，这也是为了使代码可读性强，更容易理解。至此，你已经可以完成简单的条件判断了，这在以后将是相当常用的，请多加练习并尽量熟练。