第十三届蓝桥杯青少组省赛C++中级组(0423)

选择题(单选)
选择题1:20分
下列关于类中声明的变量描述正确的是(D)。
A.只属于该类
B.属于全局变量
C.任何情况下都可被该类所有实例共享
D.属于该类,某些情况下也可被该类不同实例所共享
选择题2:20分
下列对抽象类描述正确的是(D)。
A.抽象类没有构造方法
B.抽象类必须提供抽象方法
C.抽象类可以通过new关键字直接实例化
D.有抽象方法的类一定是抽象类
选择题3:20分
二进制减法11101101-11001001(C)。
A.10111011
B.11001001
C.100100
D.10101111
选择题4:20分
以下数据结构中,能够按照“先进后出”原则存取数据的是(A)。
A.栈    B.队列    C.二又树    D.循环队列
选择题5:20分
下列对int *p[3]描述正确的是(B)。
A.p[3]表示数组的第3个元素的值,是int类型的值
B.p是一个具有3个元素的指针数组,每个元素是一个int 类型指针
C.p是一个指向数组的指针,所指向的数组是3个int 类型元素
D.p是一个指向某数组中第3个元素的指针,该元素是int 型变量

编程题1:统计数字(30分)
题目描述:
给定一个正整数N,找出3到N之间的正整数中,个位数为3的有多少个。
例如:N=25,3至25之间个位数为3的有3、13、23,一共有3个。
输入描述:
输入一个正整数N(3≤N≤99993)输出描述:
输出一个整数,表示3到N之间的正整数中,个位数为3的个数(包括3和N)
样例输入:
25
样例输出:
3

#include 
#include 
using namespace std;
int main()
{
	int n,ans=0;
	cin>>n;
	for(int i=3;i<=n;i++){
		if(i%10==3)
			ans++;
	}
	cout<

编程题2:字母组合(40分)
题目描述:
给定N个小写字母,然后将N个小写字母按照字典排序后组合成一个字符串并输出。
例如N=4,4个小写字母分别为c,d,a,c,按照字典排序后组合成的字符串为:accd
输入描述:
第一行输入一个正整数N(2 第二行输出N个小写字母,且小写字母之间以一个空格隔开
输出描述:
将N个小写字母按照字典排序后组合成一个字符串并输出
样例输入:
4
c d a c
样例输出:
accd

#include 
#include 
#include 
using namespace std;
char a[105];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i>a[i];
	sort(a,a+n);
	cout<

编程题3:组合(50分)
题目描述:
某商家将一种汤圆按照数量不同,分装成N种规格来售卖。这样的售卖方式会限制一些数量的汤圆不能买到。
例如:
N=2,2种规格的汤圆分别装3个和5个,这种情况下限制了1,2,4,7四种数量的汤圆不能买到。
给出N及N种规格的汤圆数量,请计算出有多少种数量的汤圆不能买到,如果有无限种数量的汤圆不能买到就输出“-1”。
输入描述:
第一行输入一个正整数N(1 第二行输入N个各不相同的正整数(1<正整数<100),表示每种规格的汤圆数量,且正整数之间以一个空格隔开
输出描述:
输出在这种情况下有多少种汤圆数量是不能买到的,如果有无限种数量的汤圆不能买到就输出“-1”
样例输入:
2
3 5
样例输出:
4

#include 
#include 
#include 
using namespace std;
int n,a[25],f[10005],g;
int gcd(int a,int b){
	if (a%b==0) return b;
	else return gcd(b,a%b);
}
int main()
{
	cin>>n>>a[0];
	g=a[0];
	f[a[0]]=1;
	for(int i=1;i>a[i];
		g=gcd(g,a[i]);
		f[a[i]]=1;//标记a[i]能被取到
	}
	//n个数字如果不能互质 
	//则不能组合的数字有无限个
	if(g!=1){
		cout<<-1<

编题4:帮助(60分)
题目描述:
已知有M名需要帮助的贫困学生,及每名学生购买图书的金额;和N位愿意提供帮助的志愿者,及每名志愿者愿意帮助的金额。
现N名志愿者认领贫困生进行帮助,每人可以认领贫困学生的名额不限,但如果志愿者愿意帮助的金额小于每名贫困生购买图书的金额,那么该志愿者不能认领贫困学生。请你计算出这些志愿者最多可以认领多少名贫困学生(一名学生只能被一名志愿者认领)。
例如:M=5,N=2
5名贫困学生购买图书金额分别是:200、145、240、50、45,2名志愿者帮助金额分别为150、300。则最多可以认领4名学生。(金额300的志愿者认领200、50、45这3名学生,金额150的志愿者认领145这1名学生)
输入描述:
第一行输入一个正整数M(1 第二行输入M个正整数(10<正整数<300),表示每名贫困生需要购买的图书金额,正整数之间一个空格隔开
第三行输入一个正整数N(1 第四行输入N个正整数(10<正整数<10000),表示N名志愿者帮助的金额,正整数之间一个空格隔开
输出描述:
输出一个整数,表示N名志愿者最多可以认领多少名贫困学生
样例输入:
5
200 145 240 50 45
2
150 300
样例输出:
4

#include 
#include 
#include 
using namespace std;
int m,n,a[205],b[55],cnt;
void dfs(int p,int sum){
	if(p>m) return;
	for(int i=1;i<=n;i++){//被选走的情况
		if(b[i]>=a[p]){
			b[i]-=a[p];
			cnt=max(cnt,sum+1);
			dfs(p+1,sum+1);
			b[i]+=a[p];
		}
	}
	dfs(p+1,sum);//不选的情况
}
int main()
{
	cin>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	dfs(1,0);//从第1本书开始搜索,已赞助0人
	cout<

编程题5:路线(80分)
题目描述:
有一个旅游景区,景区中有N个景点,景点以数字1到N编号,其中编号为N的景点为游客服务中心所在地。景区中有M条连接路线,每条路线连接两个景点。
已知:
1)一个景点可以被多条路线连接;
2)景点之间的连接路线都可以双向行走;
当给出N个景点和M条连接路线,及M条路线的连接关系,请你计算出从编号1到编号N-1的每一个景点,到达游客服务中心至少需要经过几条路线,如果某个景点不能到达游客服务中心则输出“-1”。
例如:N=5,M=4,4条路线的连接关系为:1<->2、1<->3、2<->4、2<->5,
景点1到达景点5(游客服务中心)至少经过2条路线(路线2、路线4);
景点2到达景点5(游客服务中心)至少经过1条路线(路线4);
景点3到达景点5(游客服务中心)至少经过3条路线(路线1、路线2、路线4);
景点4到达景点5(游客服务中心)至少经过2条路线(路线3、路线4);

第十三届蓝桥杯青少组省赛C++中级组(0423)_第1张图片
输入描述:
第一行输入两个正整数N和M(4<=N<=100,1<=M<=100),N表示景点个数,M表示路线条数,两个正整数之间一个空格隔开
接下来输入M行,每行包括两个正整数S,E(1≤S≤N,1≤E≤N,S!=E),两个正整数之间一个空格隔开,表示编号S和编号E的两个景点有一条路线连接
输出描述:
一行输出多个整数。按照1到N-1的编号顺序,分别输出每个景点到达编号N(游客服务中心),经过几条路线可以到达,如果某个景点不能到达则输出“-1”,整数之间一个空格隔开
样例输入:
5 4
1 2
1 3
2 4
2 5
样例输出:
2 1 3 2

#include 
#include 
#include 
#include 
using namespace std;
int n,m,s,e;
int a[110][110];//邻接矩阵
int p[110];//每个点的距离
int v[110];//是否经过
struct node{
	int id,len;
};
queue q;
void bfs(int t){
	q.push(node{t,0});
	v[t]=1;p[t]=0;
	while(!q.empty()){
		node tt=q.front();
		q.pop();
		for(int i=1;i>n>>m;
	for(int i=1;i<=m;i++){
		cin>>s>>e;
		a[s][e]=1;
		a[e][s]=1;
	}
	bfs(n);
	for(int i=1;i

编程题6:奖品(100分)
题目描述:
有一个N*M的矩阵方格,其中有些方格中有奖品,有些方格中没有奖品。小蓝需要从N*的矩阵中选择一个正方形区域,如果所选的正方形区域的一个对角线方格中都有奖品,其他方格都没有奖品,就会获得所选区域中的所有奖品,否则不能获得奖品。
当给出N和M的值,及N*M的矩阵方格中摆放的奖品情况(0表示方格中没有奖品,1表示方格中有奖品),请你帮助小蓝找出一个正方形区域,能够获得数量最多的奖品,并将奖品数输出。
例如:N=5,M=6,奖品情况如下:

第十三届蓝桥杯青少组省赛C++中级组(0423)_第2张图片
选择上图红色正方形区域,可以获得最多的4个奖品。
输入描述:
第一行输入两个整数N和M(1≤N≤100,1≤M≤100),N表示矩阵的行数,M表示矩阵的列数,两个整数之间一个空格隔开,接下来输入M行,每行包括M个0或者1(0表示方格中没有奖品,1表示方格中有奖品),0或者1之间一个空格隔开
输出描述:
输出一个整数,表示最多可以获得的奖品数
样例输入:
5 6
1 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 1
1 0 1 0 0 0
样例输出:
4

#include 
#include 
#include 
#include 
using namespace std;
int n,m,a[105][105],dp[105][105],maxn;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(a[i][j]==1 ){
				int flag=0;
				for (int x=i-1;x>=i-dp[i-1][j-1];x--)
					if(a[x][j]==1){
						flag=1;break;
					}
				for (int y=j-1;y>=j-dp[i-1][j-1];y--)
					if(a[i][y]==1){
						flag=1;break;
					}
				if(flag==0) dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=1;
				maxn=max(maxn,dp[i][j]);
			}
		}
	cout<