第十一届蓝桥杯省赛C/C++B组题目及部分题解

第十一届蓝桥杯省赛C/C++B组题目及部分题解
发布日期:   2022-01-18

真题链接：点这里

填空题

试题A：门牌制作（5分）

问题描述：

思路简述：

简单模拟

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int cnt(int n){
	int ans=0;
	while(n){
		if(n%10==2)ans++;n/=10;
	}
	return ans;
}
int main(){
	int ans=0;
	for(int i=1;i<=2020;++i)
		ans+=cnt(i);
	cout<<ans<<endl;
	return 0;
}

参考结果：

624

试题B：既约分数（5分）

问题描述：

思路简述：

简单模拟

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
// 返回a和b的最大公约数
int main(){
	int n=2020,ans=0;
	for(int i=1;i<n;++i)
		for(int j=i+1;j<=n;++j)
			if(gcd(i,j)==1)ans+=2;
	cout<<ans+1<<endl;
	// 1/1也算哦 
	return 0;
}

参考结果：

2481215

试题C：蛇形填数（10分）

问题描述：

思路简述：

解法一：

第20行第20列位于斜着数第 20*2-1=39行，找到39行的首和尾两个数，进行计算742+(780-742)/2=761。

代码：
1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main(){
	int n=39,a=0,sum=0;
	for(int i=1;i<=n;++i){
		a++;sum+=a;cout<<sum<<endl;
	}
	cout<<endl<<(sum-a+1)+a/2<<endl;
	return 0;
}

解法二：

简单模拟。用二维vectorv来存储这斜着数39行内容。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<vector> 
using namespace std;
int main(){
	int n=39;
	vector<vector<int>>v(n,vector<int>(n));
	int x=0,y=0,num=0;
	for(int i=0;i<n;++i){
		for(int j=0;j<=i;++j){
			v[x][y]=++num;
			if(j==i){ //到这一斜行的右端点 
				if(i&1)++x; 
				else ++y;
			}
			else{
				if(i&1)++x,--y;
				else ++y,--x;				
			}
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n-i;++j)cout<<v[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl<<v[19][19]<<endl;	
	return 0;
}

参考结果：

761

试题D：跑步锻炼（10分）

问题描述：

思路简述：

模拟题。用mon存储第i月的日数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector> 
using namespace std;
int main(){
	vector<int>mon{0,31,28,31,30,31,30,31,31,30,31,30,31};
	int y=2020,m=10,d=1;
	int ans=0,week=6;
	// week 记录今天是星期几
	for(int i=2000;i<=y;++i){ // i,j,k 枚举年月日 
		for(int j=1;j<=12;++j){
			int end=mon[j];
			if((i%400==0||i%4==0&&i%100!=0)&&j==2)end++;
            // 闰年2月29天
			for(int k=1;k<=end;++k){
				ans++;
				if(k==1||week==1)ans++;
				week=week==7?1:week+1; // 若为星期日则转为星期一
				if(i==y&&j==m&&k==d){
					cout<<ans<<endl;return 0;
				}
			}
		}
	}
	return 0;
}

参考结果：

8879

试题E：七段码（15分）

问题描述：

思路简述：

解法一：

枚举 2^n^种情况。

  • 只有一管灯亮符合条件
  • 若x灯亮，并且与x连接的其他管不亮，不符合条件
  • 最后扣除4管灯亮，2管灯连在一块的不符合条件的情况（abde,facd,bcef）
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int main(){
	int ans=0; 
	for(int a=0;a<2;++a){
		for(int b=0;b<2;++b){
			for(int c=0;c<2;++c){
				for(int d=0;d<2;++d){
					for(int e=0;e<2;++e){
						for(int f=0;f<2;++f){
							for(int g=0;g<2;++g){
								int sum=a+b+c+d+e+f+g;
								if(!sum)continue;
								else if(sum==1){
									ans++;
								}
								else{
									int flag=0;
									if(a&&!b&&!f)flag=1;
									if(b&&!a&&!g&&!c)flag=1;
									if(c&&!b&&!g&&!d)flag=1;
									if(d&&!c&&!e)flag=1;
									if(e&&!d&&!f&&!g)flag=1;
									if(f&&!a&&!e&&!g)flag=1;
									if(g&&!f&&!e&&!b&&!c)flag=1;
									if(!flag)ans++;								
								}
							}
						}
					}
				}
			}
		} 
	}
	cout<<ans-3<<endl; //减去abde,facd,bcef这三种情况 
	return 0;
}

解法二：

dfs + 并查集

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<vector>
using namespace std;
const int n=7;
vector<vector<int>>mp(n,vector<int>(n));
vector<int>v(n);
vector<int>f(n);
void un(int a,int b){
	mp[a][b]=1;mp[b][a]=1;
}
int ans=0;
int find(int a){ // 找集合的根节点 
	if(a!=f[a])f[a]=find(f[a]); 
	return f[a];
}
void dfs(int c){
	if(c==7){
		for(int i=0;i<n;++i)f[i]=i; // 初始化 
		for(int i=0;i<n;++i){ // 遍历所有可能亮灯的数码管 
			for(int j=i+1;j<n;++j){
				if(mp[i][j]&&v[i]&&v[j]){ 
				// i,j右边且i,j两管都亮 
					int a=find(i),b=find(j);
					if(a!=b)f[b]=a;	// 合并两集合 
				}
			}
		}		
		int cnt=0;
		for(int i=0;i<n;++i)
			if(v[i]&&f[i]==i)cnt++;
		if(cnt==1)ans++; // 所有亮灯都属于同一个集合 
		return;
	}
	v[c]=1; // 亮灯 
	dfs(c+1);
	v[c]=0; // 灭灯 
	dfs(c+1);、
}
int main(){
	// 0~6 --> a~g
	// 连接能通的边
	un(0,1);un(0,5);
	un(1,2);un(1,6);
	un(2,6);un(2,3);
	un(3,4);
	un(4,5);un(4,6);
	un(5,6);
	dfs(0);
	cout<<ans<<endl;
	return 0;
}

图解：

转载自[点这里](https://blog.csdn.net/m0_46272108/article/details/109157960?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.pc_relevant_default&utm_relevant_index=2)

参考结果：

80

程序题

试题F：成绩统计（15分）

答题链接：点这里

问题描述：

image-20220118153342496

image-20220118160019369

  • 样例输入

    1
    2
    3
    4
    5
    6
    7
    8
    7
    80
    92
    56
    74
    88
    100
    0

  • 样例输出

    1
    2
    71%
    43%

思路简述：

简单模拟

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream> 
using namespace std;
int main(){
	int n,score,pass=0,excellent=0;cin>>n;
	for(int i=0;i<n;++i){
		cin>>score;
		if(score>=60)pass++;
		if(score>=85)excellent++;
	}
	cout<<(int)(pass*100.0/n+0.5)<<"%"<<endl;
	cout<<(int)(excellent*100.0/n+0.5)<<"%"<<endl;
	return 0;
}

试题G：回文日期（20分）

答题链接：点这里

问题描述：

  • 样例输入

    1
    20200202

  • 样例输出

    1
    2
    20211202
    21211212

思路简述：

枚举当前日期~`99999999`

判断当前i是否符合日期规范

若日期有效，接着判断日期是否为回文串

若为回文串，接着判断是否为ababbaba型

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
vector<int>mon{0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isYear(int y){ // 判断是不是闰年 
	return y%4==0&&y%100!=0||y%400==0;
}
bool judgeDate(int y,int m,int d){ // 判断该日期是否有效 
	if(m>12)return 0; // 是月份>12不正确哦 
	if(isYear(y)&&m==2)return d<=29; // 闰年的二月份 
	return d<=mon[m];
}
int main(){
	int n,f1=1,f2=1;cin>>n;
	for(int i=n+1;i<=99999999;++i){
		int y=i/10000; // 年 
		int m=i/100%100; // 月 
		int d=i%100; // 日 
		if(!judgeDate(y,m,d))continue;
		if(!f1&&!f2)break; // 都找到啦 
		string a=to_string(i); // 转成字符串 
		string b=a;
		reverse(b.begin(),b.end()); 
		if(a==b){ // 回文字符串 
			if(f1){
				cout<<i<<endl;f1=0;
			}
			// ababbaba型 
			if(a[0]==a[2]&&a[1]==a[3]&&a[1]!=a[2]&&f2){
				cout<<i<<endl;f2=0;
			}	
		}		
	}	 
	return 0;
}

试题H：子串分值和（20分）

答题链接：点这里

问题描述：

image-20220118224708880

  • 样例输入

    1
    ababc

  • 样例输出

    1
    28

  • 样例说明

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    子串 f值
    a     1
    ab    2
    aba   2
    abab  2
    ababc 3
     b    1
     ba   2
     bab  2
     babc 3
      a   1
      ab  2
      abc 3
       b  1
       bc 2
        c 1

思路简述：

用v来存储26个字母最后一次出现的位置

假设每个区间都是第一个出现的字母有贡献值，则贡献值为与左边相同字母的距离*右边字母个数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include<vector>
using namespace std; 
typedef long long ll;
vector<int>v(26);
// 最后一次出现i+'a'的位置 
int main(){
	string s;cin>>s;
	ll ans=0;
	for(int i=0;i<26;++i)v[i]=-1; // 初始化 
	ll n=s.length();
	for(int i=0;i<n;++i){
		ans+=(i-v[s[i]-'a'])*(n-i);
		v[s[i]-'a']=i;
	}
	cout<<ans<<endl;
	return 0;
}

试题I：平面切分（25分）

答题链接：点这里

问题描述：

  • 样例输入

    1
    2
    3
    4
    3
    1 1
    2 2
    3 3

  • 样例输出

    1
    6

思路简述：

  • 只能过部分样例，一个小想法，但是用AcWing 提交wrong answer了

先用set去点重复的点，接着遍历每个点，计算每个点与前几个点的斜率A和截距B ，计算不重复的{A，B}对个数，当前点与前几个点将平面分为个数+1部分

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<set> 
using namespace std;
set<pair<double,double>>p; 
//用set储存每条边(不重复) 
double a[1001],b[1001];
int main(){
	int n,ans=2,cnt=0;cin>>n;
	double x,y;
	for(int i=0;i<n;++i){
		cin>>x>>y;p.insert({x,y});
	} 
	n=p.size(); 
	set<pair<double,double>>::iterator it;
	for(it=p.begin();it!=p.end();++it)
		a[cnt]=it->first,b[cnt++]=it->second;
	for(int i=1;i<n;++i){
		set<pair<double,double>>st;
		//储存第i条线与之前的交点坐标 
		for(int j=i-1;j>=0;--j){
			if(a[i]==a[j])continue; 
			x=(b[j]-b[i])/(a[i]-a[j]); //交点的x坐标 
			y=a[i]*x+b[i]; //交点的y坐标 
			st.insert({x,y});
		}
		ans+=st.size()+1;
	}	
	cout<<ans<<endl;
	return 0; 
}

试题J：字串排序（25分）

答题链接：点这里

问题描述：

  • 样例输入1

    1
    4

  • 样例输出1

    1
    bbaa

  • 样例输入2

    1
    100

  • 样例输出2

    1
    jihgfeeddccbbaa

思路简述：

不会哦

==欢迎各位大佬在评论区发表哦==

文章作者: Wsy
文章链接: http://example.com/2022/01/18/di-shi-yi-jie-lan-qiao-bei-sheng-sai-ti-mu-ji-bu-fen-ti-jie/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Wsy !
第十一届蓝桥杯省赛C/C++B组题目及部分题解
赏
  目录