第 12 届蓝桥杯 C++ 青少组中 / 高级组省赛 2021 年 4 月 24 日真题

一、选择题

第 1 题 单选题

题目：在 C++ 中下列哪个不属于字符型常量 ( )｡
A. ‘a’
B. ‘\x2A’
C. ‘@’
D. “F”

答案：D
解析：字符型常量使用单引号括起单个字符（如 A、C），或转义字符（如 B 中的十六进制转义字符）。D 选项 “F” 使用双引号，属于字符串常量，而非字符型常量。

第 2 题 单选题

题目：以下变量定义不正确的是 ( )｡
A. int a=8, b, c;
B. float c=1.233;
C. int if;
D. char d='i';

答案：C
解析：C 选项中 “if” 是 C++ 的关键字（用于条件判断），不能作为变量名。其他选项均符合变量定义规则：A 定义多个整型变量；B 定义浮点型变量并初始化；D 定义字符型变量并赋值。

第 3 题 单选题

题目：已知 “int n=9;”，则执行语句 “n*=n+=n%=2;” 后，n 的值为 ( )｡
A. 4
B. 1
C. 8
D. 18

答案：A
解析：运算符优先级从右到左（赋值运算符结合性为右结合）：

1. n%=2：n=9%2=1，n=1；
2. n+=1：n=1+1=2；
3. n*=2：n=2×2=4。
   最终 n=4，选 A。

第 4 题 单选题

题目：二进制加法 11010 + 10110 的和为 ( )｡
A. 110000
B. 11000
C. 101110
D. 111010

答案：A
解析：二进制逐位相加（逢二进一）：

plaintext

  11010（26）  
+ 10110（22）  
= 110000（48）  

计算过程：最低位 0+0=0，次低位 1+1=10（写 0 进 1），第三位 0+1+1=10（写 0 进 1），第四位 1+0+1=10（写 0 进 1），最高位 1+1+1=11（写 1 进 1），最终结果 110000，选 A。

第 5 题 单选题

题目：C++ 中函数的返回值类型是由 ( )｡
A. 调用该函数的主调用函数类型决定的
B. return 语句中的表达式类型决定的
C. 定义该函数所指的数据类型决定的
D. 系统自动决定的

答案：C
解析：函数定义时声明的返回值类型（如int func()中的int）决定了函数的返回值类型。return语句的表达式会被强制转换为该类型，与调用函数无关，选 C。

二、编程题

第 6 题 问答题 字符串

题目：给定一个字符串，倒序输出。
输入：字符串（长度 2<S<100）
输出：倒序字符串

第 6 题 问答题 字符串（难度降低版）

题目：给定一个字符串abc，倒序输出。要求使用for循环和数组输出倒序cba

输出：倒序字符串

第 6 题 问答题 字符串（再次难度降低版）

题目：给定一个字符串abc，用数组输出a

输出：a

答案代码：

cpp

#include <iostream>
#include <string>
using namespace std;
int main() {string s;cin >> s;for (int i = s.length() - 1; i >= 0; i--) {cout << s[i];}return 0;
}

解析：从字符串末尾（索引length()-1）开始，反向遍历每个字符并输出，即可实现倒序。例如输入 “abc”，输出 “cba”。

答案代码：

cpp

#include <iostream>
using namespace std;
int main() {int n;cin >> n;cout << (1 << n) + 1 << endl;  // 2^n + 1return 0;
}

解析：

• 对折 1 次：2 段绳子重叠，剪后段数 = 2^1 +1=3；
• 对折 2 次：4 段重叠，剪后段数 = 2^2 +1=5；
• 规律：段数 = 2^n +1，其中1<<n表示 2 的 n 次方。

答案代码：

cpp

#include <iostream>
using namespace std;
bool isComposite(int num) {if (num < 4) return false;  // 4是最小合数for (int i = 2; i * i <= num; i++) {if (num % i == 0) return true;  // 存在因数i≠1和num}return false;  // 质数（如2,3,5等）
}
int main() {int n, sum = 0;cin >> n;for (int i = 4; i <= n; i++) {if (isComposite(i)) sum += i;}cout << sum << endl;return 0;
}

解析：

• 遍历 4 到 N 的每个数，判断是否为合数：若存在因数 i（2≤i≤√num），则是合数。
• 样例输入 7 时，合数为 4、6，和为 10，符合输出。

答案代码思路：

1. 计算总和 S=1+2+…+N = N (N+1)/2。
2. 设 A1 和为 x，A2 和为 S-x，差值为 | M|=|x - (S-x)|=|2x-S|，即 2x = S±M。
3. x 必须为正整数且 0<x<S（A1 和 A2 非空），故 S±M 需为偶数且 S±M>0。
4. 对每个合法的 x，计算子集和为 x 的方案数（不考虑顺序，A1 和 A2 互换算同一种）。

关键推导：
样例 N=5，S=15，M=1：

• 2x=15±1 → x=8 或 7，均为合法整数。
• 计算和为 7 和 8 的非空子集数，总方案数为 3（如样例所示）。

代码实现（动态规划）：

cpp

#include <iostream>
using namespace std;
int main() {int N, M, S = N*(N+1)/2;cin >> N >> M;int x1 = (S + M) / 2, x2 = (S - M) / 2;bool valid1 = (S + M) % 2 == 0 && x1 > 0 && x1 < S;bool valid2 = (S - M) % 2 == 0 && x2 > 0 && x2 < S;// 动态规划计算子集和为x的方案数bool dp[30*30+1] = {false};dp[0] = true;for (int i = 1; i <= N; i++) {for (int j = S; j >= i; j--) {dp[j] = dp[j] || dp[j - i];}}int count = 0;if (valid1) count += dp[x1];if (valid2) count += dp[x2];cout << count << endl;return 0;
}

解析：利用动态规划dp[j]表示和为 j 的子集是否存在，遍历每个数更新状态。最终统计合法 x 的方案数，注意排除空集（x>0 且 x<S）。

第 10 题 问答题 最大价值

题目：在时间 t 内选最多 m 种蔬菜，求最大价值（0-1 背包变种，限制物品数量）。
输入：t（总时间），m（最多种类数），m 对（时间，价值）
输出：最大价值

答案代码（二维背包）：

cpp

#include <iostream>
using namespace std;
const int MAX_T = 600, MAX_M = 50;
int dp[MAX_M+1][MAX_T+1] = {0};  // dp[k][j]: 选k种蔬菜，时间j的最大价值int main() {int t, m;cin >> t >> m;for (int i = 0; i < m; i++) {int t1, p;cin >> t1 >> p;for (int k = m; k >= 1; k--) {  // 逆序遍历种类数，避免重复选for (int j = t; j >= t1; j--) {dp[k][j] = max(dp[k][j], dp[k-1][j-t1] + p);}}}int max_val = 0;for (int k = 1; k <= m; k++) {  // 可以选1到m种for (int j = 0; j <= t; j++) {max_val = max(max_val, dp[k][j]);}}cout << max_val << endl;return 0;
}

解析：

• 状态定义：dp[k][j]表示选 k 种蔬菜，总时间不超过 j 时的最大价值。
• 转移方程：对于每种蔬菜，从后往前更新状态，避免重复选择同一种蔬菜。
• 最终答案：遍历所有可能的种类数（1 到 m）和时间（0 到 t），取最大值。

第 11 题 问答题 黑精灵与白精灵

题目：求从 (1,1) 到 (N,M) 的最短路径，可通过穿越门（进入一门后直接到另一门，不计步数，但进出各计 1 步）。
输入：矩阵大小 N,M，两门坐标 (N1,M1)、(N2,M2)
输出：最短步数，无解输出 0

答案代码思路：

1. 使用 BFS 计算起点到所有点的距离（包括两门）。
2. 计算不经过门的最短距离：起点到终点的 BFS 距离。
3. 计算经过门的两种路径：
   • 起点→门 1→门 2→终点：距离 = 起点到门 1 的距离 + 1（进门 1） + 门 2 到终点的距离 + 1（出门 2）
   • 起点→门 2→门 1→终点：距离 = 起点到门 2 的距离 + 1 + 门 1 到终点的距离 + 1
4. 取所有合法路径的最小值，若无法到达则输出 0。

关键步骤：

• BFS 函数：返回从起点 (x1,y1) 到终点 (x2,y2) 的最短距离，不可达返回 - 1。
• 处理门的位置：确保门不是起点或终点，且两门不同。

代码框架：

cpp

#include <iostream>
#include <queue>
using namespace std;
struct Point { int x, y; };
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int bfs(int n, int m, int sx, int sy, int ex, int ey) {bool visited[101][101] = {false};queue<Point> q;q.push({sx, sy});visited[sx][sy] = true;int step = 0;while (!q.empty()) {int size = q.size();while (size--) {Point p = q.front(); q.pop();if (p.x == ex && p.y == ey) return step;for (int i = 0; i < 4; i++) {int nx = p.x + dir[i][0], ny = p.y + dir[i][1];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !visited[nx][ny]) {visited[nx][ny] = true;q.push({nx, ny});}}}step++;}return -1;  // 不可达
}int main() {int n, m, d1, d2, d3, d4;cin >> n >> m;int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;// 起点(1,1)，终点(n,m)，门A(x1,y1)，门B(x2,y2)int direct = bfs(n, m, 1, 1, n, m);  // 不经过门int toA = bfs(n, m, 1, 1, x1, y1);   // 起点到门Aint toB = bfs(n, m, 1, 1, x2, y2);   // 起点到门Bint A_to_end = bfs(n, m, x2, y2, n, m);  // 门B到终点（穿越后从门B到终点）int B_to_end = bfs(n, m, x1, y1, n, m);  // 门A到终点（穿越后从门A到终点）int viaA = (toA != -1 && A_to_end != -1) ? toA + 1 + A_to_end + 1 : -1;int viaB = (toB != -1 && B_to_end != -1) ? toB + 1 + B_to_end + 1 : -1;int min_step = 1e9;if (direct != -1) min_step = direct;if (viaA != -1) min_step = min(min_step, viaA);if (viaB != -1) min_step = min(min_step, viaB);cout << (min_step != 1e9 ? min_step : 0) << endl;return 0;
}

解析：

• 通过 BFS 计算各段路径的最短距离，考虑是否经过穿越门的两种情况（门 A→门 B 或门 B→门 A）。
• 每次经过门时，进入和离开各计 1 步，穿越过程不计步，故总步数为起点到门的距离 + 1（进门） + 另一门到终点的距离 + 1（出门）。
• 样例中，路径经过门 (3,1)→穿越到 (2,3)，总步数 4，符合计算逻辑。