第13届蓝桥杯C++青少组_国赛_中/高级组_2022年5月29日真题参考答案

一、单选题

1、在C++语言中，char类型数据占（  ）字节。

A 1

B 2

C 4

D 8

2、已知：int x = 3; int y = 2; 执行语句cout << (x -= y, x *= y+7/5); 后输出的结果是（  ）。

A 1

B 3

C 5

D 7

3、以下选项中，哪一个是面向对象程序设计中的程序组成单元(   ) 。

A 类

B 语句

C 子函数

D 主函数

4、在编写程序时，使用重载函数的目的是（  ）。

A 节省存储空间

B 共享程序代码

C 提高程序运行效率

D 使用相同函数名调用功能相似函数

5、以下选项中描述不正确的是（  ）。

A 循环队列属于线性表

B 二叉链表是二叉树的存储结构

C 带链的队列是队列的一种存储结构

D 循环链表是循环队列的一种存储结构

二、实操题

6、电线上的小鸟

题目描述：

在一根电线上落有N只小鸟，有的小鸟头向左看，有的小鸟头向右看，且每只小鸟只能看到它视线前的那一只小鸟。

给定N只小鸟头的朝向，头向左看的小鸟使用小写字母“q”表示，头向右看的小鸟用小写字母“p”表示，请你计算出N只小鸟中有多少只小鸟被0只小鸟看到，多少只小鸟被1只小鸟看到，多少只小鸟被2只小鸟看到。 

例如：N=6，6只小鸟头的朝向分别为p，q，p，p，q，q。

如图：有2只小鸟被0只小鸟看到（第3只和第6只）；有2只小鸟被1只小鸟看到（第1只和第2只）；有2只小鸟同时被2只小鸟看到（第4只和第5只），则输出三个数字分别为2，2，2。

时间限制： 1000MS

内存限制： 65536KB

输入描述

第一行输入一个正整数N（3≤N≤1000），表示有N只小鸟落在电线上

第二行输入N个字符，字符只能为“q”和“p”，“q”表示小鸟头向左看，“p”表示小鸟头向右看，字符之间以一个空格隔开

输出描述

一行输出三个整数，分别为有几只小鸟被0只小鸟看到；有几只小鸟被1只小鸟看到；有几只小鸟被2只小鸟看到；整数之间以一个空格隔开

样例输入

6
p q p p q q

样例输出

2 2 2

参考答案：4 2 0

7、报数游戏

题目描述：

某班级男生人数为X人，女生人数为Y人，现全班同学围成一个圆圈，并按照顺时针方向为每名同学编号（从1到X+Y）。现给出一个正整数K【2<K<(X+Y)】，从编号为1的同学开始顺时针方向报数，报到K的同学退出圆圈，下一名同学继续从1报数，再次报到K的同学退出圆圈。如此循环，直到剩余人数为X时游戏结束。

请你计算出游戏开始时X名男生分别应该排在什么位置，才能保证每次离开的都是女生，游戏结束时剩余X人都是男生。并将游戏开始时每名男生的位置编号按照从小到大顺序输出。

例如：X=5，Y=3，K=3，8名同学按照如下顺序排列，可以使3轮报数过后最后剩余的5名同学都为男生（蓝色为男生位置，红色为女生位置）。

故5名男同学的编号分别为2，4，5，7，8。

输入描述

输入三个正整数X，Y，K（3≤X≤100，3≤Y≤100，2<K<(X+Y)），X表示男生人数，Y表示女生人数，报数为K的同学退出圆圈，三个正整数之间以一个空格隔开

输出描述

将每名男生位置编号按照从小到大的顺序输出，编号之间以一个空格隔开

样例输入

5 3 3

样例输出

2 4 5 7 8

参考答案：由于题目要求输出每名男生的位置编号，我们可以按照题目描述进行模拟。首先，根据输入的男生人数X和女生人数Y，计算出总人数N=X+Y。然后，按照顺时针方向为每名同学编号，从1到N。接着，从编号为1的同学开始报数，每次报到K的同学退出圆圈，下一名同学继续从1报数，直到剩余人数为X时游戏结束。在模拟过程中，我们需要记录每次退出圆圈的同学的编号，并判断其性别。如果退出的同学是女生，则保留其编号；如果退出的同学是男生，则跳过。最后，将剩余的男生编号按照从小到大的顺序输出。

8、最少问题

题目描述：

河面上有N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如木桩上的数字为2，青蛙可以跳跃一个木桩也可以跳跃两个木桩）。请你帮助青蛙计算出从第一个木桩跳跃到最后一个木桩最少需要跳跃几次。

例如：N=5，5个木桩上的数字分别为2，1，5，1，3。

第一次跳跃，青蛙从第一个木桩跳跃到第三个木桩，共跳了2个木桩；

第二次跳跃，青蛙从第三个木桩跳跃到最后一个木桩，共跳了2个木桩；

故最少需要跳跃2次可到达最后一个木桩 。

输入描述

第一行输入一个正整数N（5≤N≤100），N表示河面上的木桩个数

第二行输入N个正整数（1≤正整数≤1000），表示每个木桩上的数字，正整数之间以一个空格隔开（输入的正整数顺序为木桩的排列顺序，第一个正整数为第一个木桩上的数字）

输出描述

输出一个整数，表示青蛙最少需要跳跃几次可到达最后一个木桩

样例输入

5
2 1 5 1 3

样例输出

2

参考答案：```#include #include #include using namespace std;int main() int N;cin >> N;vector nums(N);for (int i = 0; i < N; i++) {cin >> nums[i];}int max_jumps = 0;int curr_jumps = 0;int curr_pos = 0;while (curr_pos < N - 1) {int next_pos = curr_pos + nums[curr_pos];if (next_pos >= N - 1) {max_jumps++;curr_pos = N - 1;} else {int min_jumps = nums[curr_pos] + 1;for (int i = curr_pos + 1; i <= min(curr_pos + nums[curr_pos], N - 1); i++) {min_jumps = min(min_jumps, nums[i] + 1);}curr_jumps += min_jumps;max_jumps = max(max_jumps, curr_jumps);curr_pos = next_pos;}}cout << max_jumps << endl;return 0;```

9、翻卡片

题目描述：

小蓝在玩翻卡片游戏，每张卡片一面写着大写字母“A”，另一面写着大写字母“B”。首先将卡片排成一个N*N的矩阵。有的卡片是A面朝上，有的卡片是B面朝上。

现给定N的值，及N*N矩阵中每张卡片的状态，请你帮助小蓝挑选一张B面的卡，翻转成A面，使得翻转后的上、下、左、右四个方向相连的A面卡片最多，并将相连最多的卡片数量输出。

例如：N=3，3*3的矩阵中的卡片状态如下：

选择红框内那张B面卡片，翻转为A面，可以使翻转后四个方向相连的A面卡片最多，为5张。

输入描述

第一行输入一个正整数N（2≤N≤50），表示矩阵的行数和列数

第二行开始输入N行，每行输入N个字符（‘A’或者‘B’），表示矩阵中卡片状态，字符之间以一个空格隔开 

输出描述

输出一个整数，表示翻转后矩阵中上、下、左、右四个方向相连的最多A面卡片张数

样例输入

3
A B B
A B A
B A B

样例输出

5

参考答案：```#include #include using namespace std;int count(vector>& matrix, int i, int j) int count = 0;if (i > 0 && matrix[i - 1][j] == 'A') count++;if (i < matrix.size() - 1 && matrix[i + 1][j] == 'A') count++;if (j > 0 && matrix[i][j - 1] == 'A') count++;if (j < matrix[0].size() - 1 && matrix[i][j + 1] == 'A') count++;return count;int main() int N;cin >> N;vector> matrix(N, vector(N));for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> matrix[i][j];}}int maxCount = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (matrix[i][j] == 'B') {int count = count(matrix, i, j) + 1;maxCount = max(maxCount, count);}}}cout << maxCount << endl;return 0;```

10、金箍棒

题目描述：

淘气的悟空变出了N根高度各不相同的金箍棒（1≤高度≤1000），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短1个高度或者变长1个高度。

现在悟空想通过施法将K（K≤N）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使K根相邻的金箍棒高度变为相同。

例如：N=3，K=2，3根金箍棒初始高度分别为：3，6，1。

第一次对高度为3金箍棒施法变长1个高度，变为4；

第二次对高度为6金箍棒施法变短1个高度，变为5；

第三次对高度为4金箍棒施法变长1个高度，变为5；

2根相邻的金箍棒高度变为相同，最少施法3次。

输入描述

第一行输入两个正整数N，K (1≤K≤N≤10000)，N表示金箍棒的根数，K表示需要将K根相邻的金箍棒高度变为相同，两个整数之间以一个空格隔开

第二行输入N个各不相同的正整数 (1≤正整数≤1000)，表示N根金箍棒的初始高度，N个整数之间以一个空格隔开

输出描述

输出一个整数，表示悟空最少需要施法几次可以使K根相邻的金箍棒高度变为相同

样例输入

3 2
3 6 1

样例输出

3

参考答案：为了使K根相邻的金箍棒高度变为相同，我们需要对金箍棒进行高度调整。由于每次只能使一根金箍棒变短或变长1个高度，我们需要考虑如何以最少的次数调整金箍棒的高度。首先，我们需要找到高度差最大的两根金箍棒。假设这两根金箍棒的高度分别为h1和h2，且h1 < h2。我们可以从高度h1开始，通过连续变长的方式将高度调整到h2，或者从高度h2开始，通过连续变短的方式将高度调整到h1。这两种方式中，选择次数较少的那一种即可。具体步骤如下：1. 找到高度差最大的两根金箍棒，假设它们的高度分别为h1和h2，且h1 < h2。2. 计算高度差diff = h2 - h1。3. 如果diff是偶数，那么从h1开始，每次变长1个高度，需要diff/2次；从h2开始，每次变短1个高度，也需要diff/2次。取两者中较小的次数作为调整次数。4. 如果diff是奇数，那么从h1开始，每次变长1个高度，需要(diff+1)/2次；从h2开始，每次变短1个高度，需要diff/2次。取两者中较小的次数作为调整次数，并加1。根据上述思路，我们可以编写算法来解决这个问题。具体算法如下：1. 遍历金箍棒数组，找到高度差最大的两根金箍棒，假设它们的高度分别为h1和h2，且h1 < h2。2. 计算高度差diff = h2 - h1。3. 根据diff是偶数还是奇数，选择合适的调整方式，并计算调整次数。4. 返回调整次数。

11、路线

题目描述：

小蓝将多盆鲜花摆成一个M*N的矩阵，小蓝每天都会从左上角位置的花盆出发，给每一个花盆中的鲜花浇水。

已知：

1)每两个相邻的花盆之间的距离都相等；

2)每次小蓝浇水的路线都是走直线，不能走斜线；

3)除左上角花盆以外，其他花盆只能经过一次；

4)每盆花都浇过之后返回左上角位置。

当给出M和N的值，请你帮助小蓝找出一共有多少条路线可以满足以上条件，如果没有满足条件的路线输出0。

例如：M=3，N=4，一共有4条路线满足以上条件。

时间限制： 1000MS

内存限制： 65536KB

输入描述

输入两个正整数M，N（2≤M≤10，2≤N≤10），M表示矩阵的行数，N表示矩阵的列数，两个正整数之间以一个空格隔开

输出描述

输出一个整数，表示一共有多少条路线可以满足以上条件，如果没有满足条件的路线输出0

样例输入

3 4

样例输出

4

参考答案：```pythondef count_paths(m, n):dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):for j in range(n + 1):if i == 1 and j == 1:dp[i][j] = 1elif i == 1:dp[i][j] = dp[i][j - 1]elif j == 1:dp[i][j] = dp[i - 1][j]else:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m][n] if dp[m][n] != 0 else 0m, n = map(int, input().split())print(count_paths(m, n))```

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！