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

第1题：拼点游戏

C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌，每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌，S随机抽取n张蓝色卡牌，他们进行n回合拼点，每次两人各出一张卡牌，点数大者获得三颗巧克力，小者获得一颗巧克力，如果点数相同，每人各得二颗巧克力，使用过的卡牌不得重复使用。已知C和S取到的卡牌点数，请编程计算S最多和最少能得到多少颗巧克力。
时间限制：1000
内存限制：65536
输入
输入包含多组测试数据。 每组测试数据的第一行是一个整数n(1<=n<=1000)，接下来一行是n个整数，表示C抽到的白色卡牌的点数，下一行也是n个整数，表示S抽到的蓝色卡牌的点数。 输入的最后以一个0表示结束。
输出
对每组数据，输出一行，内容是两个整数用空格格开，分别表示S最多和最少可获得的巧克力数。
样例输入
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
样例输出
9 5
4 4
4 4

下面是使用贪心算法实现的代码示例：

#include <stdio.h>
#include <stdlib.h>int compare(const void* a, const void* b) {return *(int*)b - *(int*)a; // 降序排序
}void playGame(int C[], int S[], int n, int* maxChocolates, int* minChocolates) {qsort(C, n, sizeof(int), compare);  // 将C的卡牌按降序排序qsort(S, n, sizeof(int), compare);  // 将S的卡牌按降序排序*maxChocolates = 0;*minChocolates = 0;int i = 0;int j = 0;while (i < n && j < n) {if (C[i] > S[j]) {*maxChocolates += 3;*minChocolates += 1;i++;j++;} else if (C[i] < S[j]) {*maxChocolates += 1;*minChocolates += 1;i++;j++;} else {*maxChocolates += 2;*minChocolates += 2;i++;j++;}}while (i < n) {*minChocolates += 1;i++;}while (j < n) {*maxChocolates += 3;*minChocolates += 1;j++;}
}int main() {int n;while (scanf("%d", &n) == 1 && n != 0) {int* C = (int*)malloc(sizeof(int) * n);int* S = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++) {scanf("%d", &C[i]);}for (int i = 0; i < n; i++) {scanf("%d", &S[i]);}int maxChocolates, minChocolates;playGame(C, S, n, &maxChocolates, &minChocolates);printf("%d %d\n", maxChocolates, minChocolates);free(C);free(S);}return 0;
}

这段代码使用贪心算法来计算S最多和最少能得到的巧克力数。首先实现了一个 compare() 函数，用于降序排序卡牌的点数。然后实现了 playGame() 函数，根据题目描述的规则进行游戏，计算S最多和最少能得到的巧克力数。在游戏过程中，通过比较C和S两人出的卡牌点数来决定巧克力的分配。最后，实现了主函数，根据题目要求的输入格式，循环读取多组测试数据，调用 playGame() 函数计算结果，并输出最多和最少的巧克力数。

这段代码实现了贪心算法，并根据题目描述的输入和输出格式进行了相应的处理。你可以将题目给出的示例输入复制到代码中进行测试。

第2题：数字变换

给定一个包含5个数字（0-9）的字符串，例如 “02943”，请将“12345”变换到它。 你可以采取3种操作进行变换
（1）交换相邻的两个数字
（2）将一个数字加1。如果加1后大于9，则变为0
（3）将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次，第3种操作2次 求最少经过多少次操作可以完成变换。
时间限制：1000
内存限制：65536
输入
有最多 100,000 组数据 每组数据就是包含5个数字的字符串
输出
对每组数据，输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出-1
样例输入
12435
99999
12374
样例输出
1
-1
3
提示
由于测试数据太多，如果对每组数据都从头进行搜索，就会超时。 建议先做预处理，即以“12345”作为初始状态做一遍彻底的广搜，找出“12345”经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。

这个问题可以使用搜索剪枝技术来解决。下面是一个使用深度优先搜索（DFS）的示例代码，其中使用了剪枝来减少搜索空间：

#include <stdio.h>
#include <string.h>int minSteps = -1; // 最少操作步数，初始值为-1void dfs(char* str, int steps) {// 判断当前字符串是否为目标字符串"12345"if (strcmp(str, "12345") == 0) {if (minSteps == -1 || steps < minSteps) {minSteps = steps; // 更新最少操作步数}return;}// 如果已经超过最少操作步数或者超过操作限制次数，则剪枝返回if (minSteps != -1 && steps >= minSteps) {return;}// 对每个位置进行操作for (int i = 0; i < 5; i++) {// 操作1：交换相邻的两个数字if (i < 4) {char temp = str[i];str[i] = str[i+1];str[i+1] = temp;dfs(str, steps + 1);// 恢复字符串temp = str[i];str[i] = str[i+1];str[i+1] = temp;}// 操作2：将一个数字加1str[i] = (str[i] - '0' + 1) % 10 + '0';dfs(str, steps + 1);// 恢复字符串str[i] = (str[i] - '0' + 9) % 10 + '0';// 操作3：将一个数字加倍str[i] = (str[i] - '0') * 2 % 10 + '0';dfs(str, steps + 1);// 恢复字符串str[i] = (str[i] - '0' + 5) % 10 + '0';}
}int main() {char str[6];while (scanf("%s", str) == 1) {minSteps = -1;dfs(str, 0);printf("%d\n", minSteps);}return 0;
}

这段代码使用深度优先搜索（DFS）来遍历所有可能的操作序列。对于每个操作，首先判断当前字符串是否已经变为目标字符串 “12345”，如果是，则更新最少操作步数。然后判断是否满足剪枝条件：如果已经找到最少操作步数并且当前步数超过最少步数，则剪枝返回。接下来，按照操作要求进行交换、加1和加倍操作，并递归调用DFS函数。最后，在主函数中读取输入的字符串，调用DFS函数，并输出最少操作步数。

这段代码使用了搜索剪枝技术，通过减少搜索空间的大小，可以在给定的时间和内存限制下解决该问题。你可以将题目给出的示例输入复制到代码中进行测试。

第3题：打怪救公主

公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。
但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到0，骑士会死去。
迷宫由m*n个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。
时间限制：1000
内存限制：65536
输入
第一行为三个整数m、n和t，t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫，迷宫以m行n列的方格组成，若方格为".“则表示骑士可以通过，若方格为”#“则表示墙，骑士不能通过，若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于10（一位数）。”*“表示了骑士当前所在的位置，”+"表示公主被囚禁的位置。
输出
若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出0。
样例输入
5 6 10
…*…
.#2###
5#…4#
.##9.#
.#+…#
样例输出
4

这个问题可以使用搜索剪枝技术来解决。下面是一个使用深度优先搜索（DFS）的示例代码：

#include <stdio.h>
#include <stdbool.h>int m, n, t; // 迷宫的行数、列数和骑士的初始血量
char maze[20][20]; // 迷宫
bool visited[20][20]; // 记录迷宫中的方块是否已经访问过int maxHealth = 0; // 骑士走到公主所剩最大血量// 判断当前位置是否合法
bool isValid(int x, int y) {return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != '#';
}// 深度优先搜索
void dfs(int x, int y, int health) {if (maze[x][y] == '+') {// 骑士成功拯救公主if (health > maxHealth) {maxHealth = health;}return;}visited[x][y] = true;// 上下左右四个方向移动int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (isValid(nx, ny) && !visited[nx][ny]) {int newHealth = health - (maze[nx][ny] - '0');if (newHealth <= 0) {continue; // 骑士死亡，剪枝返回}dfs(nx, ny, newHealth);}}visited[x][y] = false; // 恢复状态
}int main() {scanf("%d %d %d", &m, &n, &t);int startX, startY; // 骑士的初始位置for (int i = 0; i < m; i++) {scanf("%s", maze[i]);for (int j = 0; j < n; j++) {if (maze[i][j] == '*') {startX = i;startY = j;}}}dfs(startX, startY, t);printf("%d\n", maxHealth);return 0;
}

这段代码使用深度优先搜索（DFS）来遍历迷宫中的所有可能路径。对于每个位置，首先判断是否为公主所在的位置，如果是，则更新骑士走到该位置时剩余的最大血量。然后判断当前位置是否合法，如果合法，则标记该位置为已访问，并继续在上、下、左、右四个方向进行移动。在每个方向上移动时，根据怪物的血量减少骑士的血量，并递归调用DFS函数。最后，在主函数中读取输入的迷宫信息，调用DFS函数，并输出骑士走到公主所在位置时所剩的最大血量。

这段代码使用了搜索剪枝技术，通过减少搜索空间的大小，可以在给定的时间和内存限制下解决该问题。你可以将题目给出的示例输入复制到代码中进行测试。

第4题：Freda的越野跑

Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。
假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？
时间限制：1000
内存限制：262144
输入
第一行1个整数N。 第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。 对于50%的数据，2<=N<=1000。 对于100%的数据，2<=N<=100000。
输出
一个整数，表示有多少对参赛者之间发生赶超事件。
样例输入
5
1 3 10 8 5
样例输出
7
提示
我们把这5个人依次编号为A,B,C,D,E，速度分别为1,3,10,8,5。 在跑步过程中： B,C,D,E均会超过A，因为他们的速度都比A快； C,D,E都会超过B，因为他们的速度都比B快； C,D,E之间不会发生赶超，因为速度快的起跑时就在前边。

这个问题可以使用贪心算法来解决。贪心算法是一种策略性的算法，每一步都选择当前最优解，以期望得到全局最优解。对于这个问题，我们可以观察到，一个人只能被速度更快的人超过，不能被速度较慢的人超过。因此，我们可以从最后一名参赛者开始，依次向前遍历，统计每个参赛者被超过的次数。

下面是一个使用贪心算法的示例代码：

#include <stdio.h>int main() {int N; // 参赛者的数量scanf("%d", &N);int speeds[N]; // 参赛者的速度for (int i = 0; i < N; ++i) {scanf("%d", &speeds[i]);}int count = 0; // 赶超事件的数量int maxSpeed = speeds[N - 1]; // 当前最大速度（从最后一名参赛者开始）for (int i = N - 2; i >= 0; --i) {if (speeds[i] > maxSpeed) {count++; // 当前参赛者被超过} else {maxSpeed = speeds[i]; // 更新最大速度}}printf("%d\n", count);return 0;
}

这段代码首先读取输入的参赛者数量N以及每个参赛者的速度。然后，通过从最后一名参赛者开始向前遍历的方式，统计每个参赛者被超过的次数。在遍历过程中，使用变量maxSpeed记录当前最大速度，如果当前参赛者的速度大于maxSpeed，则表示该参赛者被超过，将count加1；否则，更新maxSpeed为当前参赛者的速度。最后，输出count作为赶超事件的数量。

你可以将题目给出的示例输入复制到代码中进行测试。