RyanLi 的博客 - 学习
type: channel
link: https://blog.ryanli.top/index.php/category/learning/
description: 学习。
items: 14. 深度优先搜索
items: 13. 二分
items: 12. 贪心
items: 11. 递推与递归
items: 10. 暴力枚举
items: 8. 高精度的基本运算
items: 9. 排序
items: HSYZ 1 月月赛题解
items: HSYZ 冬季测试题解
items: HSYZ 12 月月赛题解

14. 深度优先搜索
type: item
date: 2025-06-30T23:11:50+08:00
description: 本文中将涉及一个新的专用术语——合法。这里的合法指的并非“符合法律”，而是“符合规则、符合条件”之意。之后我们提到“合法”一词，也都是这个意思。我们已经学习过了暴力枚举算法——枚举出所有可能的情况，然后判断或者统计，从而解决问题。然而，枚举全部元素的效率如同愚公移山，无法应对数据范围稍大的情形，有时甚至连编写代码都很困难。此时，我们就需要引入一个新的算法了——搜索。此搜索非彼搜索，与百度等联网搜索引擎无关。洛谷 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 位都已…

13. 二分
type: item
date: 2025-06-10T16:35:00+08:00
description: 请注意，如无特殊说明，本文默认序列的下标从 $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…

12. 贪心
type: item
date: 2025-06-10T16:34:00+08:00
description: 请注意，如无特殊说明，本文默认序列的下标从 $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(…

11. 递推与递归
type: item
date: 2025-04-10T13:01:09+08:00
description: 有些目标是宏大的，比如要在 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; }许多问题也可以套用斐波那契数列，比如假定每对大兔每月能生产一对小兔…

10. 暴力枚举
type: item
date: 2025-03-24T17:19:37+08:00
description: 算法的世界高深莫测，但是很多问题的解决方法简单而粗暴枚举出所有可能的情况，然后判断或者统计，从而解决问题。在很多程序设计比赛中，有许多比较简单的题目是可以通过枚举暴力解决的；而有的更具有挑战性的题目虽然有更巧妙的解法，但依然可以使用枚举，暴力地完成部分任务。本文将介绍一些枚举与暴力策略，这是非常基础而且重要的，但是对初学者来说还是会有一些挑战。请务必理解本章之前的所有知识后再开始本章的学习。枚举就是根据提出的问题，一一列出该问题的所有可能的解，并在逐一列出的过程中，检验每个可能解是否是问题的真正解，如果是就采纳这个解，如果不是就继续判断下一个。枚举法一般比较直观，容易理解，但由于要检查所有的可能解，因此运行效率较低。能够用枚举法解决的题目往往是最简单的一类题目。这种题目具有以下特点：枚举范围是有穷的。检验条件是确定的。验证复杂的程序的正确性，可写功能一致的暴力对照程序，并构造小规模输入数据，比较二者输出。这一过程称作对拍，在赛场上是非常实用的查错技巧。算法问题的分类一般而言，算法问题可以分为两类。模拟问题构造具体描述，使用计算机还原现实规则。每一步的行为大多是简单而确定的，只需按照既定指示行动。常基于数据结构，优化单步操作的复杂度。求解问题在全部的可能性中，搜索可行或最优解。解是不确定的，需要枚举 / 遍历 / 检索以尝试所有可能性。常使用迭代、搜索等算法求解，优化主要为记忆化、剪枝。循环枚举循环是最简单的枚举方案。我们将基于几个例题，讲解循环枚举的思路，并简介几种优化：基于数学的优化。基于剪枝的优化。技巧：打表法。有一个 $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)$ 时间内计算答案，…

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$ …

HSYZ 1 月月赛题解
type: item
date: 2024-02-03T09:44:08+08:00
description: 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 { cou…

HSYZ 冬季测试题解
type: item
date: 2024-02-03T09:43:26+08:00
description: 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$ 天：由 …

HSYZ 12 月月赛题解
type: item
date: 2024-02-03T09:42:00+08:00
description: 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。假设这个数组为 $v…