2024年9月第15届蓝桥杯C++编程青少组(国赛-中高级)真题(含答案)

2024年9月第15届蓝桥杯C++编程青少组(国赛_中高级)真题(含答案)一、单选题。1.定义inta[5]={1,2,3,4,5},*p=a+2;下列哪项与其他选项输出的结果不相同？A.cout<<a[1]+2;B.cout<<*(p++);C.cout<<p[1];D.cout<<*(a+3);标准答案：B。2.题(3e8)16A.(1101.1)B.(14.4)C.(d.8)D.(12.6)标准答案：B。3.设栈s初始为空，元素的入栈顺序为c、d、e、f，出栈顺序为c、e、f、d、a，则栈s的容量最少是（）。A.3B.4C.5D.6标准答案：B。4.下列关于类的说法，正确的是（）。A.类的成员变量和成员函数的访问权限默认是公有的B.类中的静态成员函数可以访问其他非静态成员C.类的构造函数和析构函数都可以被重载D.类的私有成员变量可以被类中的成员函数访问标准答案：D。5.表达式ceil(-120%47/8.0)的结果是（）。A.2B.3C.-3D.-4标准答案：C。二、编程题。6.给定一个奇数n和一个大写字母Center,生成一个n*n的字符矩阵。字符矩阵由大写字母和'.'(注意:'.'为英文句号)组成，并且所有大写字母组成一个n行的萎形，菱形的中心位置为大写字母Center,菱形中的大写字母规律参照”下列三组样例。输入样例1：参考程序：#include<bits/stdc++.h>usingnamespacestd;constintN=1010;chars[N][N],ch;intn;intmain(){cin>>n>>ch;intdta=ch-'A',centerx=n/2+1,centery=n/2+1;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){intd=abs(i-centerx)+abs(j-centery)if(d>dta||d>n/2)cout<<'.';elsecout<<char('A'+dta-d);}cout<<endl;}return0;}7.有两排石头，每排n颗，从左到右依次排开，每颗石头的颜色为黄色或者绿色。每次可以选择第一排的任意一颗石头与第二排的任意一颗石头交换位置。请计算最少需要交换多少次才能使每一列石头的颜色都相同；如果无论交换多少次都无法使每一列石头的颜色都相同，则输出-1。例如：n=3，每排3颗石头；第一排3颗石头的颜色从左到右依次是黄、绿、绿：第二排3颗石头的颜色从左到右依次是绿、绿、黄：其中一种最少交换次数的方案如下：1)先将第一排的第3颗石头与第二排的第3颗石头交换位置。2)再将第一排的第3颗石头与第二排的第1颗石头交换位置。此时每一列石头的颜色都相同，故至少需要交换2次。输入格式：本题每个测试点包含多组测试数据第一行包含一个整数T(1≤T≤300)，表示数据组数接下来T组数据，每组数据第一行输入一个整数n(1≤n≤104)，表示每排石头的数量。第二行输入n个整数，整数只能为1或0，1表示黄色，0表示绿色，表示第一排从左到右每颗石头的颜色，整数之间以一个空格隔开。第三行输入n个整数，整数只能为1或0，1表示黄色，0表示绿色，表示第二排从左到右每颗石头的颜色，整数之间以一个空格隔开。输入样例：2310000151010101010输出样例：2-1参考程序：#include<bits/stdc++.h>usingnamespacestd;constintN=10010;inta[N],b[N],t,n;intmain(){cin>>t;while(t--){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];//读入a。for(inti=1;i<=n;i++)cin>>b[i];//读入b。intda=0,db=0;//计数器赋值为0。for(inti=1;i<=n;i++){if(a[i]!=b[i]){if(a[i])da++;//计数a需要调整的1的个数。elsedb++;//计数b需要调整的1的个数。}}if((da+db)%2){//判断能否成功，不成功就输出-1。cout<<-1<<endl;}else{intans=da/2+db/2;//按照成对进行计算,按照一对1，调整1次来计算。if(da%2)ans+=2;//有余数，符合调整2次的情况，增加2次。cout<<ans<<endl;//输出最终结果。}}return0;}8.因数：也称约数，如果整数a除以整数b，商为整数且余数为0，则称b是a的因数。例如：1、2、3、6都是6的因数。素数：也称质数，是指在大于1的自然数中，除了1和它本身以外没有其他因数的数。例如：2、3、5是素数，4、6、8不是素数。平方数：指的是可以写成某个整数的平方的数。例如：4(2^2)、9(3^2)、16(4^2)都是平方数。莫比乌斯函数μ(n)是指以下的函数：1)若n=1，则μ(n)=1。2)若n的因数中有大于1的平方数，则μ(n)=0。3)若n的因数中没有大于1的平方数，且n=P1，P2……Pk，则μ(n)=(-1)k，注：P,P…P.表示k(k≤1)个不同素数的乘积。例如：1)8的因数有1、2、4、8，其中大于1的平方数有4，所以μ(8)=0。2)15的因数有1、3、5、15，没有大于1的平方数，且15=3×5，所以μ(15)=(-1)2=1。3)30的因数有1、2、3、5、6、10、15、30，没有大于1的平方数，且30=2×3×5，所以μ(30)=(-1)3=-1。给定两个正整数m、n，请计算m到n之间(含m和n)所有整数的莫比乌斯函数值之和。输入格式：一行输入两个正整数m和n(1≤m≤n≤2×107)，整数之间以一个空格隔开。输出格式：输出一个整数，表示m到n之间(含m和n)所有整数的莫比乌斯函数值之和。输入样例：110输出样例：-1参考程序：#include<bits/stdc++.h>usingnamespacestd;intm,n;constintN=2e7+10;intcnt[N],a[N],s[N];boolt[N];intmain(){cin>>m>>n;for(inti=2;i<=n/2;i++){if(cnt[i])continue;for(intj=i*2;j<=n;j+=i)//埃筛，计算因子数量。cnt[j]++;}for(inti=2;i*i<=n;i++){intc=i*i;for(intj=c;j<=n;j+=c)//记录有完全平方数因子的数。t[j]=1;}a[1]=1;for(inti=2;i<=n;i++){if(t[i])continue;//有完全平方数因子函数值为0。if(cnt[i]%2||cnt[i]==0)a[i]=-1;//奇数个质因子或者质数函数值-1。elsea[i]=1;}intans=0;for(inti=m;i<=n;i++)ans+=a[i];cout<<ans<<endl;return0;}9.一张棋盘由n行m列的网格矩阵组成，每个网格中最多放一颗棋子。当前棋盘上已有若干棋子。所有水平方向或竖直方向上相邻的棋子属于同一连通块。现给定棋盘上所有棋子的位置，如果要使棋盘上出现两个及以上的棋子连通块，请问最少需要移除几颗棋子？如果无论怎么移除棋子都无法满足要求，则输出-1。(注：只能通过移除棋子的操作来使棋盘上出现两个及以上的棋子连通块。)由下图可知，最少需要移除2颗棋子才能使棋盘上出现两个及以上的棋子连通块。例如：n=3，m=3，3x3的棋盘示意图如下：移除后棋盘示意图如下：故答案为2。输入格式：本题每个测试点包含多组测试数据第一行包含一个整数T(1≤T≤50)，表示数据组数接下来T组数据，每组数据第一行输入两个整数和m(1≤n，m≤60)，分别表示组成棋盘的网格矩阵的行数和列数，整数之间以一个空格隔开。接下来n行，每行输入m个大写字符(字符为'G'或'L')，分别表示每个网格的情况，’G’表示有棋子，'L'表示无棋子，字符之间以一个空格隔开。输出格式：输出T行，每行一个整数，第i行的整数表示第i组数据中最少需要移除多少颗棋子才能使棋盘上出现两个及以上的棋子连通块；如果无论怎么移除棋子都无法满足要求，则输出-1。输入样例：233LGGLGGLLL44LLLLLGLLLGLLLLLL输出样例：2-1参考程序：#include<bits/stdc++.h>usingnamespacestd;constintN=110;intdx[]={-1,1,0,0},dy[]={0,0,-1,1};intt,n,m;chars[N][N];intdfn[N*N],low[N*N],tot,root;vector<int>e[N*N];boolcut;voidtarjan(intx){dfn[x]=low[x]=++tot;intchild=0;for(inty:e[x]){if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);if(low[y]>=dfn[x]){child++;if(x!=root||child>1)cut=1;}}elselow[x]=min(low[x],dfn[y]);}}intmain(){cin>>t;while(t--){cin>>n>>m;for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){cin>>s[i][j];e[i*n+j].clear();}inttotal=0;for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){if(s[i][j]=='G'){total++;for(intk=0;k<4;k++){intx=dx[k]+i,y=dy[k]+j;if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]=='G')e[i*n+j].push_back(x*n+y);}}}intcnt=0;tot=cut=0;memset(dfn,0,sizeofdfn);memset(low,0,sizeoflow);for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){if(s[i][j]=='G'&&dfn[i*n+j]==0){root=i*n+j;tarjan(i*n+j);cnt++;}}if(total==1||total==2&&cnt==1)cout<<-1<<endl;elseif(cnt>1)cout<<0<<endl;else{if(cut)cout<<1<<endl;elsecout<<2<<endl;}}return0;}10.给定包含n个整数的数列，从中选取一段连续子数列，使其元素之和能被k整除。请找出符合要求的最长连续子数列并输出其长度以及子数列本身；如果符合要求的最长连续子数列有多个，则输出起始位置最靠后的那个子数列。如果不存在符合要求的子数列，则输出-1。例如：n=7，k=7，数列为7、3、4、1、5、14、9。连续子数列{7}、{7，3，4}、{3，4}、和{5，14，9}的和都能被7整除；其中最长的连续子数列有{7，3，4}和{5，14，9}，起始位置最靠后的是{5，14，9}。故符合要求的最长连续子数列长度为3，子数列为5149。输入描述：第一行输入两个整数n和k(1≤n≤105，2≤k≤108)，整数之间以一个空格隔开。第二行输入n个整数(1≤整数≤104)，整数之间以一个空格隔开。输出描述：如果存在符合要求的最长连续子数列，则输出为两行：第一行输出一个整数，表示最长连续子数列的长度。第二行输出若干个整数，表示起始位置最靠后的最长连续子数列，整数之间以一个空格隔开。如果不存在，则输出-1。输入样例：7773415149输出样例：35149参考程序：#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;ints[N],a[N],n,k;unordered_map<int,int>mp;intl,r,ans;intmain(){cin>>n>>k;mp[0]=0;for(inti=1;i<=n;i++){cin>>a[i];s[i]=(s[i-1]+a[i])%k;if(!mp.count(s[i]))//如果之前还没有出现过记录。{mp[s[i]]=i;}else{if(ans<i-mp[s[i]])//出现过则说明这段区间是k的倍数，更新最大值。{ans=i-mp[s[i]];l=mp[s[i]],r=i;}elseif(ans==i-mp[s[i]])//区间长度一样则更新l更靠后。{if(mp[s[i]]>l){l=mp[s[i]],r=i;}}}}cout<<ans<<endl;for(inti=l+1;i<=r;i++)cout<<a[i]<<'';return0;}11.某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个节点，编号分别为1、2、3、…n。为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？例如：n=8，表示有8个节点(即道路交叉点或端点)，1到8号节点部署监控设备的费用分别为3