2024年3月蓝桥杯青少组STEMA考试C++中高级真题解析（第15届）

第一部分 选择题
第 1 题    单选题

(110010)2+(c3)16的结果是(  )。

A.(240)10

B.(11110101)2

C.(366)8

D.(f6)16

【答案】B

【解析】全部转换10进制：

B.1 * 2^7 + 1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0

= 128 + 64 + 32 + 16 + 0 + 4 + 0 + 1

= 245

C.3 * 8^2 + 6 * 8^1 + 6 * 8^0

= 3 * 64 + 6 * 8 + 6 * 1

= 192 + 48 + 6

= 246

D.(f × 16^1) + (6 × 16^0)

=246

第 2 题    单选题

表达式1000/3的结果是(   )。

A.333

B.333.3

C.334

D.333.0

【答案】A

【解析】在C++中，整数除法的结果是整数。当你用两个整数进行除法运算时，结果会被截断为一个整数，小数部分会被丢弃

第 3 题    单选题

下列选项中，判断a等于1并且b等于1正确的表达式是()。

A.!((a!=1)&&(b!=1))

B.!((a!=1)||(b!=1))

C.!(a==1)&&(b==1)

D.(a=1)&&(b=1)

【答案】B

【解析】

A. !((a!=1)&&(b!=1))

这个表达式先检查 aa 是否不等于1和 bb 是否不等于1，然后对这两个条件进行逻辑与操作。如果 aa 和 bb 都不等于1，则内部表达式为真，外部的否定操作将其变为假。如果 aa 和 bb 至少一个等于1，则内部表达式为假，外部否定操作将其变为真。这实际上是检查至少一个变量等于1。

B. !((a!=1)||(b!=1))

这个表达式检查 aa 是否不等于1或者 bb 是否不等于1，然后对这两个条件进行逻辑或操作。如果 aa 或 bb 中至少有一个不等于1，则内部表达式为真，外部的否定操作将其变为假。如果 aa 和 bb 都等于1，则内部表达式为假，外部否定操作将其变为真。因此，这个表达式确实是检查 aa 等于1并且 bb 等于1的正确方式。

C. !(a==1)&&(b==1)

这个表达式先检查 aa 是否等于1，并对该条件进行否定操作，然后检查 bb 是否等于1。这意味着即使 bb 等于1，如果 aa 等于1，整个表达式的结果都会因为对 a==1a==1 的否定操作而变为假。这并不符合我们寻找的条件，因为它不是检查 aa 和 bb 是否都等于1。

D. (a=1)&&(b=1)

这个表达式有语法错误，因为它使用了赋值运算符 = 而不是等于判断运算符 ==。因此，这不是一个有效的判断表达式。

第 4 题    单选题

定义 char a[]="His name is Jack"，请问 sizeof(a)的结果是()。

A.14

B.15

C.16

D.17

【答案】D

【解析】sizeof操作符用来获取变量或类型所占的空间大小，单位是字节。对于字符数组，sizeof将计算包括字符串的实际字符和末尾的空字符\0在内的总字节数。

给定的字符串"His name is Jack"包含16个可见字符，但是在C语言中字符串以空字符\0结尾，这意味着还有一个不可见的字符需要存储。

因此，sizeof(a)的结果为16个可见字符加上1个空字符，总共是17个字符。

第 5 题    单选题

定义 int a[]={5,1,3,8,2,9,0,6},*p=(a+3)，那么((*p)-- + *p )的值是()。

A.3

B.10

C.15

D.16

【答案】C

【解析】有一个整型数组 a[]={5,1,3,8,2,9,0,6}，然后有一个指针 p 指向数组 a 的第四个元素（由于数组索引从0开始，因此 a+3 指向 8）。

表达式 ((*p)-- + *p ) 需要按照运算顺序来计算。这里涉及到后缀减减操作符（--），它会在表达式求值后才将操作数减1。

*p 初始指向 8。((*p)--) 首先取出 *p 的值（即 8），然后将 *p 减1（此时 *p 变为 7）。接下来的 + *p 是在 *p 已经被减1后进行，所以这时 *p 是 7。

因此，表达式的值是 8 + 7 = 15。

第二部分 编程题

第 6 题    问答题

编程实现：寒假期间小明需要做完n张试卷，但他每天最多能做完m 张，请计算出小明做完n张试卷最少需要多少天？

输入描述

一行输入两个整数n和m（1≤n≤100，1≤m≤10），分别表示要完成的试卷张数，及每天最多能做完的试卷张数，整数之间以一个空格隔开

输出描述

输出一个整数，表示小明最少多少天能做完n张试卷

样例输入

10 3

样例输出

4

【样例分析】

     小明总共有10张试卷要做，而他每天能做最多3张，怎么算呢？

先算能整除的天数： 小明每天做3张，那么他3天能做9张。看看还剩下多少： 做完这9张后，小明还剩1张没做。剩下的怎么办： 即使只剩1张，小明也得花一整天来做。这就意味着他还需要额外的一天。

【解题思路】

看小明每天能做的试卷数能让他几天做完大部分试卷，然后再看他是否还需要额外的一天来完成剩下的那一点点。最后加起来，就是小明完成任务需要的总天数。

【代码步骤】

读入数据： 首先，程序需要读入两个整数 n 和 m，它们分别代表要完成的试卷总数和每天最多能完成的试卷数。

计算天数： 接着，计算小明完成所有试卷所需的最少天数。这可以通过整除操作 n / m 来实现，以确定小明能在整数天内完成的最大试卷数。但是，如果 n 不是 m 的倍数，小明还需要额外的一天来完成剩余的试卷。因此，我们还需要检查 n % m（n 除以 m 的余数）是否大于0来判断是否需要额外加一天。

输出结果： 最后，根据计算结果输出小明完成所有试卷所需的最少天数。

【实现代码】

#include <iostream>using namespace std;int main() {    int n, m; // n 是试卷总数，m 是每天最多能完成的试卷数    cin >> n >> m; // 从标准输入读取 n 和 m 的值    // 计算最少需要的天数    int days = n / m; // 首先，计算出小明不需要额外天数时能完成试卷的天数    if (n % m != 0) { // 如果还有剩余的试卷不能被 m 整除，就需要额外的一天        days += 1;    }    cout << days << endl; // 输出小明完成所有试卷所需的最少天数    return 0;}

第 7 题    问答题

编程实现：给定两个整数a，b，请统计a到b之间（包含a和b）有多少个包含数字7的回文数。

例如：a=6，b=80，6到80之间的回文数有6、7、8、 9、11、22、33、44、55、66、77，其中有2个回文数包含7（7和77）。

输入描述

一行输入两个整数a和b（1≤a≤b≤100000），整数之间以一个空格隔开

输出描述

输出一个整数，表示a到b之间（包含a和b）包含数字7的回文数的个数

样例输入

6 80

样例输出

2

【解题思路】

判断回文数

想象一下你写下一个数字，比如12321，然后你从左边读和从右边读这个数字都是一样的，这就叫做回文数。就像单词 "racecar" 一样，不管是从前往后读还是从后往前读，都是一样的。

要判断一个数字是不是回文数，可以这么做：

把这个数“翻转”过来，比如把12321变成12321（还是它自己）。比较这个翻转前后的数字，如果一模一样，那么它就是回文数。

判断包含数字7

这个就更直接了。你只需要看这个数每一个数字是不是7：

把数字拆开来，一个个看。如果发现有任何一个数字是7，那么这个数就“包含数字7”。

举个例子

假设有一个数字，比如 14741，怎么用程序来检查它呢？

判断回文数：**我们把它翻转过来变成14741，发现翻转前后一样，所以它是回文数。

判断包含数字7：**在把数字一个个看过去的时候，发现有个7在里面，所以它包含数字7。

【代码步骤】

读取输入： 首先，从标准输入读取两个整数 a 和 b，代表查找范围的开始和结束。

遍历范围内的每个数： 对于从 a 到 b 之间的每个数，需要检查它是否是回文数以及是否包含数字7。

检查回文数： 编写一个函数，判断给定的数是否是回文数。这可以通过将数转换成字符串，然后检查字符串是否从前到后读和从后到前读是相同的来实现。

检查是否包含7： 同样可以将数转换成字符串，然后检查字符串中是否包含字符'7'。

计数： 对于每个在范围内满足以上两个条件的数，增加一个计数器。

输出结果： 最后，输出计数器的值，即为答案

【代码实现】

#include <iostream>#include <string>using namespace std;// 函数：判断是否为回文数bool isHw(int n) {    string s = to_string(n);    int i = 0, j = s.length() - 1;    while (i < j) {        if (s[i] != s[j]) {            return false;        }        i++;        j--;    }    return true;}// 函数：判断是否包含数字7bool isSev(int n) {    string s = to_string(n);    return s.find('7') != string::npos; // 如果找到'7'，返回true}int main() {    int a, b;    cin >> a >> b; // 读取输入的两个整数    int count = 0; // 用于计数包含7的回文数    for (int i = a; i <= b; i++) {        if (isHw(i) && isSev(i)) {            count++; // 如果是回文数且包含7，计数器加1        }    }    cout << count << endl; // 输出结果    return 0;}

第 8 题    问答题

编程实现：给定一个字符串S，请统计S中有多少个ABB形式的子串， 以及多少种ABB形式的子串。

例如：S=“nnnseebbetoosee”，ABB形式的子串有see、 ebb、too、see,共4个；不同子串有see、ebb、too,共3种。

输入描述

输入一个长度不超过100的字符串S

输出描述

输出两个整数，分别表示S中有多少个ABB形式的子串，以及多少种ABB形式的子串，整数之间以一个空格隔开

样例输入

nnnseebbetoosee

样例输出

4 3

提示信息：

ABB形式的字符串：是由3个字符组成，其中后两个字符相同，第一个字符与后两个字符不同。如:"cbb"、"q22"、"688"都是 ABB 形式的字符串；"abc"、"wwe"、"pop"都不是 ABB 形式的字符串。子串：是指一个字符串中连续的一段字符序列。如：字符串“Hello,World!"中，"Hello"、"ello"、"World"、"or"都是该字符串的子串。

【解题思路】

1. 遍历字符串，寻找ABB形式的子串

遍历给定字符串 S 的每个字符，使用索引 i 从0开始直到 S.length() - 3（因为我们要检查当前字符及其后面两个字符，所以不需要检查最后两个字符）。对于每个字符 S[i]，检查 S[i+1] 和 S[i+2] 是否相同，并且与 S[i] 不同。如果满足条件，说明我们找到了一个ABB形式的子串。

2. 统计找到的ABB子串

使用一个计数器 totalABB 来记录找到的ABB形式子串的总数。每次发现一个ABB形式的子串时，totalABB 加1。

3. 统计不同的ABB形式子串

使用一个 set（在C++中，set 自动去重，只存储不同的元素）来存储不同的ABB形式子串。每次找到一个ABB形式的子串时，将其加入到这个 set 中。由于 set 的特性，它将自动处理重复的子串。最后，set 中元素的数量就是不同ABB形式子串的总数。

4. 输出结果

输出 totalABB 和 set 中元素的数量，这两个值分别表示找到的ABB形式子串的总数和不同的ABB形式子串的总数。

【代码实现】

#include <iostream>#include <set>#include <string>using namespace std;int main() {    string S;    cin >> S; // 读入字符串    int totalABB = 0; // ABB形式子串的总数    set<string> uniqueABB; // 存储不同的ABB形式子串    // 遍历字符串    for(int i = 0; i < S.length() - 2; i++) {        // 检查当前子串是否为ABB形式        if(S[i] != S[i+1] && S[i+1] == S[i+2]) {            totalABB++; // 找到一个ABB形式的子串            uniqueABB.insert(S.substr(i, 3)); // 加入到set中        }    }    // 输出找到的ABB形式子串的总数和不同的ABB形式子串的总数    cout << totalABB << " " << uniqueABB.size() << endl;    return 0;}

第 9 题    问答题

编程实现：给定一个由n个整数组成的数列，请将其分割成左右两部分， 要求左半部分子数列的和与右半部分子数列的和最接近，请输出这两部分子数列和的差值（取非负值）。

例如：n=5，数列中的5个整数分别是2、1、3、4、3，将其分割成左右两部分，左半部分是2、1、3，右半部分是4、 3；此时两部分子数列的和最接近，差值为1。

输入描述

第一行输入一个整数n（2≤n≤100000）

第二行输入n个整数（1≤整数≤1000），整数之间以一个空格隔开

输出描述

输出一个整数，表示这两部分子数列和的差值（取非负值）

样例输入

5

2 1 3 4 3

样例输出

1

【解题思路】

前缀和是解决这类问题的一种非常高效的方法。前缀和可以快速计算数列中任意一段的和，从而更有效地找到将数列分为两部分使其和尽可能接近的分割点。

使用前缀和的解题思路如下：

计算前缀和：首先，遍历数列一次，计算每个位置的前缀和，存储在一个数组中。前缀和数组preSum[i]表示数列中从第一个元素到第i个元素的和。

寻找最优分割点：遍历前缀和数组，找到一个点，使得这个点左侧的和与右侧的和的差值最小。具体来说，对于每个位置i，左侧的和就是preSum[i]，右侧的和可以通过总和减去preSum[i]得到。

计算并更新最小差值：在遍历的过程中，使用一个变量记录遇到的最小的差值。对于每个位置i，计算左侧和右侧的差值（取绝对值），如果这个差值小于当前记录的最小差值，则更新最小差值。

输出最小差值：遍历完成后，已经找到了最小的差值，输出这个差值即为答案。

使用前缀和，可以在O(n)的时间复杂度内完成整个过程，这对于大规模数据非常有效。

【代码实现】

#include <iostream>#include <cmath> // 用于abs函数using namespace std;const int MAX_N = 100001; // 数组大小int nums[MAX_N]; // 存储输入的数列int preSum[MAX_N]; // 存储前缀和int main() {    int n;    cin >> n;    // 初始化前缀和数组的第一个元素为0    preSum[0] = 0;    // 读入数列并计算前缀和    for (int i = 1; i <= n; i++) {        cin >> nums[i];        preSum[i] = preSum[i - 1] + nums[i];    }    int totalSum = preSum[n]; // 总和    int minDiff = totalSum; // 初始化最小差值为总和，确保第一次比较时会被替换    // 遍历前缀和数组，寻找最小差值    for (int i = 1; i <= n; i++) {        int leftSum = preSum[i]; // 左侧的和        int rightSum = totalSum - leftSum; // 右侧的和        int diff = abs(leftSum - rightSum); // 计算差值        if (diff < minDiff) {            minDiff = diff; // 更新最小差值        }    }    // 输出最小差值    cout << minDiff << endl;    return 0;}

第 10 题    问答题

编程实现：给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。

例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231；

例2：n=123，123中每位上的数字依次是1、2、3，重新排列组成的新数有312、321、231、213、132，新数中不存在小于123的正整数，故输出-1。

输入描述

输入一个正整数 n (1≤ n <2^63)

输出描述

输出一个正整数，表示符合要求的最大正整数

样例输入

312

样例输出

231

【解题思路】

将整数n转换为其字符串表示形式。从字符串的末尾开始向前查找，直到找到一个数字，该数字小于其后面的数字。这意味着我们找到了一个在重新排列后可能获得更小数字的机会。从这个数字开始，向字符串的末尾查找，找到大于该数字的最小数字。交换这两个数字。将原先找到的较小数字之后的所有数字升序排序，以确保我们得到的新数字尽可能大，但仍然小于原始数字。输出新构造的数字。如果无法找到这样的数字（即原数字是升序排列的），则输出-1。

【代码实现】

prev_permutation来直接生成小于给定数字n的最大排列。如果prev_permutation返回true，说明找到了一个符合条件的排列，直接输出这个新排列对应的整数。如果返回false，说明没有找到符合条件的排列（即输入数字已经是最小可能排列），这时输出-1。

#include <iostream>#include <string>#include <algorithm>using namespace std;int main() {    long long n;    cin >> n;    string s = to_string(n);    // 检查是否可以找到一个小于n的排列    if (prev_permutation(s.begin(), s.end())) {        cout << stoll(s) << endl;    } else {        cout << -1 << endl;    }    return 0;}

第 11 题    问答题

编程实现：靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。

当某块靶被击中后，击中者会得到 x * y * z 的积分。( y 表示被击中的靶上的数，

x表示其左侧最近且未被击中的靶上的数，z表示其右侧最近且未被击中的靶上的数。

如果其左侧不存在未被击中的靶，则x为1；如果其右侧不存在未被击中的靶，则z为1。）

计算完积分后，这块靶就会退出靶场（不在这排靶中）。

请计算击中所有靶后能得到的最高积分是多少？

例如：n=4，表示有4块靶，这4块靶上的数从左到右分别是3、2、4、6;

按照下列顺序打靶，可以得到最高积分：

1.打2号靶，得到的积分是24（3*2*4）；

2.打3号靶，得到的积分是72（3*4*6）；

3.打1号靶，得到的积分是18（1*3*6）；

4.打4号靶，得到的积分是6（1*6*1）；

最终获得的积分是120（24+72+18+6）。

输入描述

第一行输入一个整数n（1≤n≤300），表示靶场上靶的数量

第二行输入n个整数（1≤整数≤100），分别表示从左到右每块靶上的数，整数之间以一个空格隔开

输出描述

输出一个整数，表示击中所有靶后能得到的最高积分

样例输入

4

3 2 4 6

样例输出

120

【解题思路】

每次射击后靶的退出会影响左右靶的选择，可以采用一个区间DP的方法。

定义状态： dp[i][j]表示区间[i, j]内，所有靶被击中后能得到的最高积分，其中1 ≤ i ≤ j ≤ n。这意味着我们考虑的是，当只有i到j这一段靶存在时，能获得的最高积分。

转移方程： 考虑 dp[i][j] 如何通过子问题求解。如果我们选择在 [i, j] 区间内最后击中第 k 块靶（i ≤ k ≤ j），则此时的积分可以这样计算：首先，击中k靶本身能得到的积分是a[k-1]*a[k]*a[k+1]，其中a[k]是靶k上的数字，a[k-1]和a[k+1]分别是左右相邻靶上的数字（如果k是区间的边界，则相应地用1替代）。此后，这块靶退出，剩下的区间被分为了两部分[i, k-1]和[k+1, j]，这两部分内的最高积分分别是dp[i][k-1]和dp[k+1][j]。

因此，转移方程为：

dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[i-1]*a[k]*a[j+1])

其中，如果i等于1或j等于n，则a[i-1]或a[j+1]应当被视为1，因为靶场的边界外没有靶。

初始化： 对于只有一块靶的情况，即当i == j时，dp[i][i]就是a[i-1]*a[i]*a[i+1]，同样地，如果i是1或n，则相应地用1代替a[i-1]或a[i+1]。

计算顺序： 从小到大计算所有可能的区间长度，对于每个长度，遍历所有可能的起始点i，然后计算此区间内所有可能的k。

结果： 最终的结果是dp[1][n]，代表整个靶场上所有靶被击中后能得到的最高积分。

         代码实现时，我们需要对边界条件做适当处理，特别是靶场两端的情况。

#include <iostream>#include <algorithm>using namespace std;const int MAX_N = 305; // 考虑到n的范围加上两端的虚拟靶int a[MAX_N]; // 存储靶上的数，包括两端的虚拟靶int dp[MAX_N][MAX_N]; // 动态规划数组int main() {    int n;    cin >> n;    a[0] = 1; // 左边界外的靶视为1    for (int i = 1; i <= n; ++i) {        cin >> a[i];    }    a[n + 1] = 1; // 右边界外的靶视为1    // 初始化单个靶的情况    for (int i = 1; i <= n; ++i) {        dp[i][i] = a[i - 1] * a[i] * a[i + 1];    }    // 动态规划求解    for (int len = 2; len <= n; ++len) { // 靶场长度从2开始到n        for (int i = 1; i <= n - len + 1; ++i) {            int j = i + len - 1;            for (int k = i; k <= j; ++k) {                int score = dp[i][k - 1] + dp[k + 1][j] + a[i - 1] * a[k] * a[j + 1];                dp[i][j] = max(dp[i][j], score);            }        }    }    cout << dp[1][n] << endl; // 输出击中所有靶后能得到的最高积分    return 0;}

代码说明：

代码采用了一个(n+2) x (n+2)的dp数组来存储每个子问题的最优解。数组大小为n+2是因为在数组的开始和结束各自增加了一个虚拟靶，值为1，以简化边界条件的处理。对于每个长度len从1到n的区间，我们计算并更新该区间内所有可能射击方式的最高得分。这是通过枚举区间内每个可能的射击目标k来完成的。每次射击得分由dp[i][k - 1]（射击k靶之前的部分）、dp[k + 1][j]（射击k靶之后的部分）和a[i - 1] * a[k] * a[j + 1]（射击k靶得到的得分）组成。最后，dp[1][n]存储了射击整个靶场（所有靶）所能得到的最高积分，这个值被输出为结果。

本文链接：https://www.kjpai.cn/news/2024-04-17/159701.html，文章来源：网络cs，作者：利杜鹃，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！