十五届蓝桥青少C++组3月评测2024年3月中高级

STEMA考试 C++中高级试卷(24年3月10日)

一、选择题（50分）

1:(110010)2+(c3)16的结果是()。
*选择题严禁使用程序验证，选择题不答或答错都不扣分
A.(240)10  
B.(11110101)2  
C.(366)8  
D.(f6)16 
备注：此题目下标代表进制，因不支持md格式。  
参考答案：B
2:表达式1000/3的结果是()。
*选择题严禁使用程序验证，选择题不答或答错都不扣分
A.333  
B.333.3  
C.334  
D.333.0  
参考答案：A
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
4:定义 char a[]="His name is Jack"，请问 sizeof(a)的结果是()。
*选择题严禁使用程序验证，选择题不答或答错都不扣分
A.14  
B.15  
C.16  
D.17  
参考答案：D
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

二、编程题（350分）

第 1 题(20分)

时间限制：1000MS
内存限制：65536KB
题目描述：
编程实现：
寒假期间小明需要做完n张试卷，但他每天最多能做完m 张，请计算出小明做完n张试卷最少需要多少天？
输入描述
一行输入两个整数n和m（1≤n≤100，1≤m≤10），分别表示要完成的试卷张数，及每天最多能做完的试卷张数，整数之间以一个空格隔开
输出描述
输出一个整数，表示小明最少多少天能做完n张试卷
样例输入
10 3
样例输出
4
评分标准：
2分：能正确输出第一组数据；
2分：能正确输出第二组数据；
2分：能正确输出第三组数据；
2分：能正确输出第四组数据；
2分：能正确输出第五组数据。
2分：能正确输出第六组数据；
2分：能正确输出第七组数据；
2分：能正确输出第八组数据；
2分：能正确输出第九组数据；
2分：能正确输出第十组数据。  

参考答案1：

#include<bits/stdc++.h>using namespace std;int main(){  int n,m;  cin>>n>>m;  cout<<n/m+(n%m!=0);  return 0;}

参考答案2： 

#include<bits/stdc++.h>using namespace std;int main(){  int n,m;  cin>>n>>m;  cout<<(n+m-1)/m;  return 0;}

参考答案3： 

#include<bits/stdc++.h>using namespace std;int main(){  int n,m;  int ans;  cin>>n>>m;  ans=n/m;  if (n%m!=0){    ans++;  }  cout<<ans;  return 0;}

参考答案4： 

#include<bits/stdc++.h>using namespace std;int main(){  int n,m;  int ans;  cin>>n>>m;  cout<<int(ceil(1.0*n/m));  return 0;}

 第 2 题 （40分）

时间限制：1000MS
内存限制：65536KB
题目描述：
编程实现：
给定两个整数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
评分标准：
4分：能正确输出第一组数据；
4分：能正确输出第二组数据；
4分：能正确输出第三组数据；
4分：能正确输出第四组数据；
4分：能正确输出第五组数据；
4分：能正确输出第六组数据；
4分：能正确输出第七组数据；
4分：能正确输出第八组数据；
4分：能正确输出第九组数据；
4分：能正确输出第十组数据。

 参考答案：

#include<bits/stdc++.h>using namespace std;int huiwen(int n){//判断是否回文  int a=n,b=0;  while(n){    b=b*10+n%10;    n/=10;  }  return b==a;}int check(int n){//判断是否含7  while(n){    if(n%10==7) return 1 ;    n/=10;  }  return 0;}int main(){  int a,b,cnt=0;  cin>>a>>b;  for(int i=a;i<=b;i++){    if(huiwen(i) && check(i)) cnt++;  }  cout<<cnt;  return 0;}

 第 3 题 （50分）

时间限制：1000MS
内存限制：65536KB
题目描述：
提示信息：
ABB形式的字符串：是由3个字符组成，其中后两个字符相同，第一个字符与后两个字符不同。
如:"cbb"、"q22"、"688"都是 ABB 形式的字符串；
   "abc"、"wwe"、"pop"都不是 ABB 形式的字符串。

子串：是指一个字符串中连续的一段字符序列。
如：字符串“Hello,World!"
中，"Hello"、"ello"、"World"、"or"都是该字符串的子串。
编程实现：
给定一个字符串S，请统计S中有多少个ABB形式的子串， 以及多少种ABB形式的子串。
例如：S=“nnnseebbetoosee”，ABB形式的子串有see、 ebb、too、see,共4个；不同子串有see、ebb、too,共3种。
输入描述
输入一个长度不超过100的字符串S
输出描述
输出两个整数，分别表示S中有多少个ABB形式的子串，以及多少种ABB形式的子串，整数之间以一个空格隔开
样例输入
nnnseebbetoosee
样例输出
4 3
评分标准：
5分：能正确输出第一组数据；
5分：能正确输出第二组数据；
5分：能正确输出第三组数据；
5分：能正确输出第四组数据；
5分：能正确输出第五组数据；
5分：能正确输出第六组数据；
5分：能正确输出第七组数据；
5分：能正确输出第八组数据；
5分：能正确输出第九组数据；
5分：能正确输出第十组数据。

 参考答案：

#include<bits/stdc++.h>using namespace std;set <string> s;int main() {    int cnt = 0;    string a;    cin >> a;    if(a.size() < 3) {        cout << "0 0";        return 0;    }    for(int i = 0; i < a.size() - 2; i++) {        string b = a.substr(i, 3);        if(b[0] != b[1] && b[1] == b[2]) {            cnt++;            s.insert(b);        }    }    cout << cnt << " " << s.size();    return 0;}

 第 4 题 （60分）

时间限制：1000MS
内存限制：65536KB
题目描述：
编程实现：
给定一个由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
评分标准：
6分：能正确输出第一组数据；
6分：能正确输出第二组数据；
6分：能正确输出第三组数据；
6分：能正确输出第四组数据；
6分：能正确输出第五组数据；
6分：能正确输出第六组数据；
6分：能正确输出第七组数据；
6分：能正确输出第八组数据；
6分：能正确输出第九组数据；
6分：能正确输出第十组数据。
参考答案1：双指针

#include <bits/stdc++.h>using namespace std;int n;int a[100005];int main() {    cin >> n;    for (int i = 1; i <= n; i++) {            cin>>a[i];    }    int sum1=0;    int sum2=0;    int i=1;    int j=n;    while(i<=j){        if (sum1<sum2){            sum1+=a[i];            i++;        }else{            sum2+=a[j];            j--;        }    }    cout<<abs(sum1-sum2);    return 0;}

参考答案2：前缀和

#include<bits/stdc++.h>using namespace std;int n,a,s[100005],minn=2e9;int main(){cin>>n;for (int i=1;i<=n;i++) cin>>a,s[i]=s[i-1]+a;for (int i=1;i<n;i++){minn=min(abs((s[i]-s[0])-(s[n]-s[i])),minn);}cout<<minn<<endl;return 0;}

参考答案3：

#include<bits/stdc++.h>using namespace std;int n,a[1000005],sum=0,m=1e9,sum1=0;int main(){  cin>>n;  for(int i=1;i<=n;i++){    cin>>a[i];    sum+=a[i];  }  for(int i=1;i<=n;i++){    sum1+=a[i];    sum-=a[i];    m=min(abs(sum1-sum),m);  }  cout<<m;  return 0;} 

 第 5 题 编程题 （80分）

时间限制：1000MS
内存限制：65536KB
题目描述：
编程实现：
给定一个正整数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
评分标准：
8分：能正确输出第一组数据；
8分：能正确输出第二组数据；
8分：能正确输出第三组数据；
8分：能正确输出第四组数据；
8分：能正确输出第五组数据；
8分：能正确输出第六组数据；
8分：能正确输出第七组数据；
8分：能正确输出第八组数据；
8分：能正确输出第九组数据；
8分：能正确输出第十组数据。

参考答案1：贪心算法

若数字有n位，对于后i（i从2到n）位，若从i到n位为递增，则不可能调换顺序使之变小，若从i到n位不是递增，将第i+1位到第n位按降序排序，然后将第i位和后边第一比它小的数字调换一下就可以了。i越小，调后的数字减少越小。若n位都为递增，则无答案。

详见代码：

#include <bits/stdc++.h>using namespace std;string a;int main() {    cin >> a;    int len=a.length();    bool flag=0;//假定无解    for(int i=len-1;i>0;i--){        if (a[i]<a[i-1]){            for(int j=i,k=len-1;j<k;j++,k--){                swap(a[j],a[k]);            }            for(int j=i;j<=len-1;j++){                if(a[i-1]>a[j]){                    swap(a[i-1],a[j]);                    break;                }            }            flag=1;//有解            break;        }    }    if(flag==1&&a[0]!='0'){        cout<<a;    }else{        cout<<-1;    }    return 0;}

参考答案2：感谢 gamer爸爸 提供的解题思路及解题代码

将n个字符按照任意方式排列，所得到的所有组合，叫做n的全排列。这些全排列从小到大的顺序，叫做这n个数的字典序。

对于某一种排列方式，使用c++的stl库提供的prev_permutation可以获得其上一种字典序，也就是紧挨着他的，比他小的那种排列。

因此只需要用字符串接受输入，然后获取该字符串的上一个字典序就行了。

#include<bits/stdc++.h> using namespace std;int main() {  string n;  cin >> n;  if (prev_permutation(n.begin(), n.end())&&n[0]!=0)    cout << n;  else    cout << -1;}

 第 6 题 编程题 （100分）

时间限制：1000MS
内存限制：65536KB
题目描述：
编程实现：
靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。
当某块靶被击中后，击中者会得到 x * y * z 的积分。( y 表示被击中的靶上的数，
×表示其左侧最近且未被击中的靶上的数，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
评分标准：    
10分：能正确输出第一组数据；
10分：能正确输出第二组数据；
10分：能正确输出第三组数据；
10分：能正确输出第四组数据；
10分：能正确输出第五组数据；
10分：能正确输出第六组数据；
10分：能正确输出第七组数据；
10分：能正确输出第八组数据；
10分：能正确输出第九组数据；
10分：能正确输出第十组数据。

参考答案：感谢 gamer爸爸 提供的解题思路

动态规划

定义状态：dp[i][j] = x 表示：打掉 i 和 j 之间（不包括 i 和 j）的所有靶子，可以获得的最大积分为 x。

状态转移方程：枚举i和j中间的每一个数k，i+1<=k<=j-1

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[k] * nums[i] * nums[j])

根据题目要求，我们可以在数组的最左、最右两端增加两个积分为1，且不能打的靶，并让i，j的范围在1~n之间变化，最后要求最大值就是dp[0][n+1]，也就是最左、最右两个我们增加的两个靶之间全打掉可以获得的最大值。

#include<bits/stdc++.h>using namespace std;int n;int a[305];int dp[305][305];//打掉ij之间所有靶子可以获得的最大积分（不含i，j）int main() {    cin>>n;    for(int i=1;i<=n;i++){        cin>>a[i];    }    a[0]=1;    a[n+1]=1;    for(int i=n+1;i>=0;i--){        for(int j=i+1;j<=n+1;j++){            for(int k=i+1;k<j;k++){                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[k]*a[i]*a[j]);            }        }    }    cout<<dp[0][n+1];    return 0;}

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