2022年09月 C/C++（四级）真题解析#中国电子学会#全国青少年软件编程等级考试

第1题：最长上升子序列

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
时间限制：11000
内存限制：65536
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4

要解决最长上升子序列的问题，可以使用动态规划的方法。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>int max(int a, int b) {return (a > b) ? a : b;
}int longestIncreasingSubsequence(int arr[], int n) {int dp[1001] = {0};int maxLen = 1;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}return maxLen;
}int main() {int n;scanf("%d", &n);int arr[1001];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}int longestLen = longestIncreasingSubsequence(arr, n);printf("%d\n", longestLen);return 0;
}

该代码使用一个一维数组dp来记录以每个位置上的元素为结尾的最长上升子序列的长度。

首先，将dp数组的初始值全部设为1，因为任意单个元素本身就是一个长度为1的上升子序列。

然后，从第二个位置开始，遍历数组中的每个元素，对于每个元素，再次遍历它之前的元素，如果找到比当前元素小的元素，说明可以将当前元素加入到以该元素结尾的子序列中，更新dp数组的值。

最后，遍历dp数组找到最大的值，即为最长上升子序列的长度。

第2题：神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。
时间限制：10000
内存限制：65536
输入
输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。
输出
输出不同的选择物品的方式的数目。
样例输入
3
20
20
20
样例输出
3

要解决神奇的口袋问题，可以使用递归的方法进行求解。

以下是使用C语言实现的代码：

#include <stdio.h>int count = 0;void magicalPocket(int items[], int n, int idx, int sum) {if (sum == 0) {count++;return;}if (idx == n || sum < 0) {return;}magicalPocket(items, n, idx + 1, sum - items[idx]);magicalPocket(items, n, idx + 1, sum);
}int main() {int n;scanf("%d", &n);int items[21];for (int i = 0; i < n; i++) {scanf("%d", &items[i]);}magicalPocket(items, n, 0, 40);printf("%d\n", count);return 0;
}

该代码使用递归函数magicalPocket来尝试不同的选择物品的方式。

递归函数的参数包括物品数组items、物品数量n、当前处理的物品索引idx和目标总体积sum。

函数首先判断如果目标总体积为0，则表示找到一种选择方式，将count计数器加1并返回。

然后判断如果当前处理的物品索引为n或目标总体积小于0，则返回。

接下来，递归调用函数，分为两种情况：选择当前物品或不选择当前物品。

选择当前物品时，递归调用函数并更新目标总体积为sum - items[idx]，同时将物品索引加1。

不选择当前物品时，递归调用函数并保持目标总体积为sum，同时将物品索引加1。

最后，主函数调用magicalPocket函数，并输出count计数器的值，即为不同的选择物品的方式的数目。

第3题：滑雪

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
时间限制：1000
内存限制：65536
输入
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
输出
输出最长区域的长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25

要解决滑雪问题，可以使用动态规划的方法。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdbool.h>int max(int a, int b) {return (a > b) ? a : b;
}int longestSlide(int grid[][100], int R, int C, int r, int c, int dp[][100]) {if (dp[r][c] != -1) {return dp[r][c];}int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int maxLen = 1;for (int i = 0; i < 4; i++) {int newRow = r + directions[i][0];int newCol = c + directions[i][1];if (newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && grid[newRow][newCol] < grid[r][c]) {maxLen = max(maxLen, longestSlide(grid, R, C, newRow, newCol, dp) + 1);}}dp[r][c] = maxLen;return maxLen;
}int main() {int R, C;scanf("%d %d", &R, &C);int grid[100][100];int dp[100][100];for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {scanf("%d", &grid[i][j]);dp[i][j] = -1;}}int maxLength = 0;for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {maxLength = max(maxLength, longestSlide(grid, R, C, i, j, dp));}}printf("%d\n", maxLength);return 0;
}

该代码使用一个二维数组dp来记录从每个位置开始的最长滑坡的长度，以避免重复计算。

首先，将dp数组的初始值全部设为-1，表示尚未计算。

然后，遍历输入的区域二维数组，对于每个位置(r, c)，调用longestSlide函数进行递归计算以该位置为起点的最长滑坡长度。

在longestSlide函数中，首先判断如果dp[r][c]已经计算过，则直接返回其值。

然后，定义四个方向的移动数组directions，分别为上、下、左、右。

接下来，遍历四个方向，计算新的行和列的位置，并判断新位置是否在合法范围内且高度小于当前位置的高度。

如果满足条件，则递归调用longestSlide函数并更新maxLen的值。

最后，将dp[r][c]设为maxLen并返回。

最后，主函数遍历整个区域二维数组，找到最大的滑坡长度，并输出。

第4题：删除数字

娇娇一年级了，刚刚学会了识数和比大小。有一天，她在黑板上写上了一串数字：2，1，2，5，4。接着她擦掉了第一个2，发现剩下1，2，4都在自己的位置上，即：1在第1位，2在第2位，4在第4位。
娇娇希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣，想知道最多能有几个数在自己的位置上，请你帮帮她!
时间限制：1000
内存限制：65536
输入
第一行，一个整数 TestNum( ≤ 10)，表示测试数据的组数。 接下来每组数据有两行，第一行：一个整数n( ≤ 1000)，第二行：n个正整数(≤ 1000)。
输出
对于每组测试数据，输出一个数表示答案。
样例输入
3
5
2 1 2 5 4
7
2 2 3 2 4 5 3
10
1 1 2 2 3 3 4 4 5 5
样例输出
3
4
5
提示
第一组测试数据：擦掉第一个数，1 2 4 有 3 个数在自己的位置上。
第二组测试数据：擦掉第4个、第7个数，2 3 4 5 有 4 个数在自己的位置上。
第三组测试数据：每种相同的数擦掉一个，1 2 3 4 5 有 5 个数在自己的位置上。

要解决删除数字的问题，可以使用贪心算法的思路。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdbool.h>int max(int a, int b) {return (a > b) ? a : b;
}int countNumbers(int numbers[], int n) {int count = 0;for (int i = 0; i < n; i++) {if (numbers[i] == i + 1) {count++;}}return count;
}int maxCountNumbers(int numbers[], int n) {int maxCount = 0;for (int i = 0; i < n; i++) {int temp = numbers[i];numbers[i] = -1;maxCount = max(maxCount, countNumbers(numbers, n));numbers[i] = temp;}return maxCount;
}int main() {int TestNum;scanf("%d", &TestNum);while (TestNum--) {int n;scanf("%d", &n);int numbers[1000];for (int i = 0; i < n; i++) {scanf("%d", &numbers[i]);}int result = maxCountNumbers(numbers, n);printf("%d\n", result);}return 0;
}

该代码使用两个函数来解决问题。

首先，countNumbers函数用于计算给定数字数组中有多少个数字在自己的位置上。

函数遍历数组，对于每个位置i，如果数字numbers[i]的值等于i + 1，则计数器count加1。

最后，返回计数器count的值。

接下来，maxCountNumbers函数用于找到删除数字后最多有多少个数字在自己的位置上。

函数遍历数组，对于每个位置i，将数字numbers[i]暂存到temp变量中，并将该位置的值设为-1，表示删除。

然后，调用countNumbers函数计算删除数字后剩下的数字数组中有多少个数字在自己的位置上，并更新最大值maxCount。

最后，将该位置的值恢复为temp，继续下一次循环。

最后，主函数根据输入的测试组数，循环读取每组测试数据，并调用maxCountNumbers函数计算答案并输出。