一、实操题
1、珠心算测验
【问题描述】
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
最近老师出了一些测验题，请你帮忙求出答案。
【输入】
输入文件名为 count.in。
输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
【输出】
输出文件名为 count.out。
输出共一行，包含一个整数，表示测验题答案。
【输入输出样例】
【样例说明】
由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的两个不同的数。
【数据说明】
对于 100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过 10,000。
参考答案：```bash#include
解析：【喵呜刷题小喵解析】：
本题目要求计算在一个正整数集合中，有多少个数等于集合中另外两个（不同的）数之和。可以使用两层循环遍历集合中的数，然后计算两个数的和，查看和是否存在于集合中。如果存在，则答案加一。
具体实现时，可以使用一个哈希表（unordered_map）来存储集合中的数，以便快速查找。对于每个数，遍历集合中除了它之外的所有数，计算它们的和，并在哈希表中查找该和是否存在。如果存在，则将答案加一。最终输出答案即可。
上述程序使用 C++ 实现，包括读入数据、遍历集合、计算答案和输出结果等步骤。程序的时间复杂度为 O(n^2)，其中 n 是集合中数的个数。由于题目中给出的数据范围较小，因此程序可以在较短时间内完成计算。
2、比例简化
【问题描述】
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1）的前ᨀ下，A’/B’ ≥ A/B且 A’/B’ - A/B 的值尽可能小。
【输入】
输入文件名为 ratio.in。
输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
【输出】
输出文件名为 ratio.out。
输出共一行，包含两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例。
【输入输出样例】
【数据说明】
对于 100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100，A/B ≤ L。
参考答案：```1 3```
解析：【喵呜刷题小喵解析】：
首先，我们需要理解题目的要求。题目要求我们将支持人数 A 和反对人数 B 的比例 A/B 化简为 A'/B'，其中 A' 和 B' 需要满足以下条件：
1. A' 和 B' 均不大于 L。
2. A' 和 B' 互质（即它们的最大公约数为 1）。
3. A'/B' ≥ A/B 且 A'/B' - A/B 的值尽可能小。
我们可以从第一个条件开始考虑。因为 A 和 B 都是给定的，我们需要找到两个数 A' 和 B'，使得 A'/B' 是 A/B 的简化形式，且 A' 和 B' 不大于 L。
观察 A/B 的形式，我们可以发现，如果 A' 和 B' 都是 A 和 B 的约数，那么 A'/B' 就是 A/B 的简化形式。同时，为了使得 A' 和 B' 互质，A' 和 B' 都应该是 A 和 B 的质因数分解中的质因数。
由于 A 和 B 的范围都很大（最大可以到 1,000,000），我们需要找到 A 和 B 的最大公约数，然后将 A 和 B 分别除以这个最大公约数，得到 A' 和 B'。这样，A' 和 B' 就是 A 和 B 的简化形式，且 A' 和 B' 互质。
但是，题目中还有一个条件，即 A' 和 B' 均不大于 L。如果 A' 和 B' 大于 L，我们需要重新考虑 A' 和 B' 的取值。
由于 A'/B' 是 A/B 的简化形式，且 A'/B' - A/B 的值要尽可能小，我们可以尝试将 A' 和 B' 调整为不大于 L 的最大整数，使得 A'/B' 尽可能接近 A/B。
对于上面的例子，A = 1498，B = 902，L = 100。我们可以先找到 A 和 B 的最大公约数，然后将 A 和 B 分别除以这个最大公约数，得到 A' 和 B'。但是，由于 A' 和 B' 都大于 L，我们需要重新考虑 A' 和 B' 的取值。由于 A/B ≈ 1.66，且 L = 100，我们可以尝试将 A' 和 B' 取为 100 的约数，使得 A'/B' 尽可能接近 1.66。最终，我们得到 A' = 1，B' = 3，满足题目要求。
3、
螺旋矩阵
【问题描述】
一个 n 行 n 列的螺旋矩阵可由如下方法生成：
从矩阵的左上角（第 1 行第 1 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 1, 2, 3, ... ,
，便构成了一个螺旋矩阵。
下图是一个 n = 4 时的螺旋矩阵。
现给出矩阵大小 n 以及 i 和 j，请你求出该矩阵中第 i 行第 j 列的数是多少。
【输入】
输入文件名为 matrix.in。
输入共一行，包含三个整数 n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。
【输出】
输出文件名为 matrix.out。
输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。
【输入输出样例】
【数据说明】
对于 50%的数据，1 ≤ n ≤ 100;
对于 100%的数据，1 ≤ n ≤ 30,000，1 ≤ i ≤ n，1 ≤ j ≤ n。
参考答案：对于给定的矩阵大小n以及i和j，我们需要确定螺旋矩阵中第i行第j列的数。
解析：【喵呜刷题小喵解析】：
首先，我们需要理解螺旋矩阵的生成方式。螺旋矩阵的生成过程是从矩阵的左上角开始，初始时向右移动，如果前方是未曾经过的格子，则继续前进，否则右转。重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, ...。
根据题目描述，我们需要找到第i行第j列的数。由于螺旋矩阵的生成方式，第i行第j列的数可能是矩阵中的任何一个数，具体取决于i和j在螺旋矩阵中的位置。
因此，我们需要先确定螺旋矩阵的大小n，然后找到第i行第j列在螺旋矩阵中的位置。由于螺旋矩阵的生成方式，我们可以通过模拟生成螺旋矩阵的过程，找到第i行第j列的数。
然而，这种方法的时间复杂度较高，对于较大的n，可能会超时。因此，我们需要寻找一种更高效的算法来解决这个问题。
观察螺旋矩阵的生成过程，我们可以发现，当螺旋矩阵的生成方向发生变化时，对应的数会按照特定的规律变化。例如，当从右向左移动时，对应的数会按照递增的规律变化；当从上向下移动时，对应的数会按照递增的规律变化；当从下向上移动时，对应的数会按照递减的规律变化；当从左向右移动时，对应的数会按照递减的规律变化。
因此，我们可以通过判断第i行第j列在螺旋矩阵中的位置，以及对应的生成方向，来确定第i行第j列的数。具体算法如下：
1. 首先，我们需要确定螺旋矩阵的大小n。
2. 然后，我们需要找到第i行第j列在螺旋矩阵中的位置。
3. 根据第i行第j列在螺旋矩阵中的位置，我们可以确定对应的生成方向。
4. 根据对应的生成方向，我们可以确定第i行第j列的数。
由于这种方法的时间复杂度较低，可以在较短时间内得到正确的答案。
4、 子矩阵
【问题描述】
给出如下定义：
1. 子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。
例如，下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如右图所示。
2. 相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
3. 矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。
本题任务：给定一个 n 行 m 列的正整数矩阵，请你从这个矩阵中选出一个 r 行 c 列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。
【输入】
输入文件名为 submatrix.in。
第一行包含用空格隔开的四个整数 n，m，r，c，意义如问题᧿述中所述，每两个整数之间用一个空格隔开。
接下来的 n 行，每行包含 m 个用空格隔开的整数，用来表示问题᧿述中那个 n 行 m 列的矩阵。
【输出】
输出文件名为 submatrix.out。
输出共 1 行，包含 1 个整数，表示满足题目描述的子矩阵的最小分值。
【输入输出样例 1】
【输入输出样例 1 说明】
该矩阵中分值最小的 2 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、
【输入输出样例 2】
【输入输出样例 2 说明】
该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成，选取的分值最小的子矩阵为
【数据说明】
参考答案：对于这个问题，我们可以使用动态规划的方法来解决。首先，我们需要计算原矩阵中每对相邻元素之差的绝对值之和，然后在这个基础上，我们可以使用动态规划来找到最小的子矩阵分值。具体的步骤如下：1. 创建一个二维数组dp，dp[i][j]表示选取原矩阵的前i行和前j列的所有元素所能得到的最小分值。2. 对于dp[i][j]，我们可以将其拆分为两个部分：选取前i-1行和前j-1列的所有元素所能得到的最小分值dp[i-1][j-1]，以及选取第i行第j列的元素所能得到的分值。3. 对于选取第i行第j列的元素所能得到的分值，我们可以遍历第i行的前j-1个元素，对于每个元素，我们计算其与第i行第j列的元素之差的绝对值，并将其加入到dp[i][j]中。4. 最后，我们返回dp[n][m]即可得到最小的子矩阵分值。
解析：【喵呜刷题小喵解析】：
这个问题可以使用动态规划来解决，主要是因为这个问题具有最优子结构性质。也就是说，我们可以通过计算原矩阵中每对相邻元素之差的绝对值之和，然后在这个基础上，使用动态规划来找到最小的子矩阵分值。
具体来说，我们可以创建一个二维数组dp，dp[i][j]表示选取原矩阵的前i行和前j列的所有元素所能得到的最小分值。然后，我们可以使用动态规划的思想，通过计算dp[i][j]的值，来得到最小的子矩阵分值。
在这个过程中，我们需要注意到，选取第i行第j列的元素所能得到的分值，可以拆分为选取前i-1行和前j-1列的所有元素所能得到的最小分值dp[i-1][j-1]，以及选取第i行第j列的元素所能得到的分值。这个思路可以帮助我们快速计算出dp[i][j]的值，从而得到最小的子矩阵分值。
最终，我们返回dp[n][m]即可得到最小的子矩阵分值，这就是我们的答案。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
