第十一届蓝桥杯大赛第二场省赛c++b组

试题A:门牌制作

【问题描述】

​ 小蓝要为一条街的住户制作门牌号。
​ 这条街一共有2020位住户,门牌号从1到2020编号。
​ 小蓝制作门牌的方法是先制作О到9这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌1017需要依次粘贴字符1、0、1、7,即需要1个字符0,2个字符1,1个字符7。
​ 请问要制作所有的1到2020号门牌,总共需要多少个字符2?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

暴力破解

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll ans;
void solve(int x){
	while(x){
		if(x%10==2){
			ans++;		
		}
		x/=10;
	}
} 
int main() {
  	for(int i=1;i<=2020;i++){
  		solve(i);
	  }
	  cout<<ans;
    return 0;
    
}

试题B:既约分数

【问题描述】

​ 如果一个分数的分子和分母的最大公约数是1,这个分数称为既约分数。

​ 例如,言,是,吉,都是既约分数。
​ 请问,有多少个既约分数,分子和分母都是1到2020之间的整数(包括1和2020)?

【答案提交】

​ 这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

辗转相除法

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll ans;
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
int main() {
  	for(int i=1;i<=2020;i++){
  		for(int j=1;j<=2020;j++){
  			  if(gcd(i,j)==1){
  			  		ans++;
				}
		  }
	  }
	  cout<<ans;
    return 0;
    
}

试题C:蛇形填数

【问题描述】

如下图所示,小明用从1开始的正整数“蛇形”填充无限大的矩阵。
1 2 6 7 15 ....
3 5 8 14 ...

4 9 13 ...
10 12 .
11
容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

1.找规律

通项公式为2*n*(n-1)+1

2

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll ans;
int a[50][50];
int cnt=1;
int main() {
	int x,y;
    for(int i = 1 ; i <= 40; i++)
	{
        if(i % 2==1 )
		{
			
            for(x = i, y = 1; x >= 1 && y <= i; x--, y++)
                a[x][y] = cnt++;
        }
        else
		{
            for(x = 1, y = i; x <= i && y >= 1; x++, y--)
                a[x][y] = cnt++;
        }
    }
    cout<<a[20][20];
    return 0;
    
}

试题D:跑步锻炼

【问题描述】

​ 小蓝每天都锻炼身体。
​ 正常情况下,小蓝每天跑1千米。如果某天是周一或者月初(1日),为了激励自己,小蓝要跑2千米。如果同时是周一或月初,小蓝也是跑﹖千米。
​ 小蓝跑步已经坚持了很长时间,从2000年1月1日周六(含)到2020年10月1日周四(含)。请问这段时间小蓝总共跑步多少千米?

【答案提交】

​ 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

SB题,跳过

试题E:七段码

【问题描述】

​ 小蓝要用七段码数码管来表示一种特殊的文字。

​ 上图给出了七段码数码管的一个图示,数码管中一共有7段可以发光的二极管,分别标记为 a, b, c,d, e,f,g·
​ 小蓝要选择一部分二极管(至少要有一个)发光来表达字符。在设计字符的表达时,要求所有发光的二极管是连成一片的。
​ 例如: b发光,其他二极管不发光可以用来表达一种字符。
​ 例如: c发光,其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符,尽管看上去比较相似。
​ 例如: a, b, c, d, e 发光,f,g不发光可以用来表达一种字符。
​ 例如: b, f 发光,其他二极管不发光则不能用来表达一种字符,因为发光的二极管没有连成一片。
​ 请问,小蓝可以用七段码数码管表达多少种不同的字符?

【答案提交】

​ 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

dfs枚举子集+并查集判断连通块

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;


const int N=10;
int p[N],f[10][10],b[N]; 
int ans=0;
int find(int x){
	if(x!=p[x]){
		p[x]=find(p[x]);
	}
	return p[x];
}
void dfs(int pos){
	//并查集判断是否为连通块 
	if(pos>7){
		for(int i=1;i<=7;i++){
			p[i]=i;
		}
		for(int i=1;i<=7;i++)
			for(int j=1;j<=7;j++)
				if(f[i][j]){
				int fx=find(i),fy=find(j);
				if(fx!=fy&&b[i]&&b[j]){
					p[fy]=fx;
				}
			}
		int h=0;
		for(int i=1;i<=7;i++){
			if(p[i]==i&&b[i]){
				h++;
			}
		}
		if(h==1)
			ans++;
		return;
	}
	
	b[pos]=1;
	dfs(pos+1);
	b[pos]=0;
	dfs(pos+1);
}


int main() {
	
	f[1][2]=f[2][1]=1;
	f[1][6]=f[6][1]=1;
	f[2][3]=f[3][2]=1;
	f[2][7]=f[7][2]=1;
	f[3][7]=f[7][3]=1;
	f[3][4]=f[4][3]=1;
	f[4][5]=f[5][4]=1;
	f[5][7]=f[7][5]=1;
	f[5][6]=f[6][5]=1;
	f[6][7]=f[7][6]=1;
	
	dfs(1);
	cout<<ans;
    return 0;
    
}

试题F:成绩统计

时间限制: 1.0s内存限制: 256.0MB本题总分:15分

【问题描述】

​ 小蓝给学生们组织了一场考试,卷面总分为100分,每个学生的得分都是一个0到100的整数。
​ 如果得分至少是60分,则称为及格。

​ 如果得分至少为85分,则称为优秀。

​ 请计算及格率和优秀率,用百分数表示,百分号前的部分四舍五入保留整数。

【输入格式】

​ 输入的第一行包含一个整数n,表示考试人数。
​ 接下来n行,每行包含一个0至 100的整数,表示一个学生的得分。

【输出格式】

​ 输出两行,每行一个百分数,分别表示及格率和优秀率。百分号前的部分四舍五入保留整数。

【样例输入】

7
80

92

56

74

88

100

0

【样例输出】

​ 71%
​ 43%

【评测用例规模与约定】

​ 对于50%的评测用例,1≤n ≤ 100。

​ 对于所有评测用例,1≤n ≤ 10000.

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N=10005;

int main(){
	int n;
	cin>>n;
	int god=0,ok=0;
	int t;
	for(int i=0;i<n;i++){	
		cin>>t;
		
		if(t>=60){
			ok++;
		}
		 if(t>=85){
			god++;
		}		
	}	
		double godx=god*1.0/n*100;
		int gody=god*100/n;
		double okx=ok*1.0/n*100;
		int oky=ok*100/n;
		
		if(okx>=(oky+0.5)){
			cout<<oky+1<<'%'<<endl; 
		}else{
			cout<<oky<<'%'<<endl;
		}
		
		if(godx>=(gody+0.5)){
			cout<<gody+1<<'%'<<endl; 
		}else{
			cout<<gody<<'%'<<endl;
		}
	return 0;
}

试题G:回文日期

时间限制: 1.0s内存限制: 256.0MB本题总分:20分

【问题描述】

​ 2020年春节期间,有一个特殊的日期引起了大家的注意:2020年2月2日。因为如果将这个日期按“yyyymmdd”的格式写成一个8位数是20200202,恰好是一个回文数。我们称这样的日期是回文日期。
​ 有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同,因为不到2年之后就是下一个回文日期:20211202即 2021年12月2日。
​ 也有人表示20200202并不仅仅是一个回文日期,还是一个ABABBABA型的回文日期。对此小明也不认同,因为大约100年后就能遇到下一个ABABBABA 型的回文日期: 21211212即2121年 12月12日。算不上“千年一遇”,顶多算“千年两遇”。
​ 给定一个8位数的日期,请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。

【输入格式】

输入包含一个八位整数N,表示日期。

【输出格式】

输出两行,每行1个八位数。第一行表示下一个回文日期,第二行表示下一个ABABBABA型的回文日期。

【样例输入】

20200202

【样例输出】

20211202

21211212

【评测用例规模与约定】

对于所有评测用例,10000101 ≤ N ≤89991231,保证N是一个合法日期的8位数表示。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;

const int N=10005;

int main(){
	int n;
	cin>>n;
	int m=n+1;
	int anss;
	int flag=1;
	while(1){
		vector<int> ans;
		int t=m;
		while(t){
			ans.push_back(t%10);
			t=t/10;
		}
		if((ans[0]==ans[7])&&(ans[1]==ans[6])&&(ans[2]==ans[5])&&(ans[3]==ans[4])){
			if(flag){
				for(int i=0;i<8;i++){
				cout<<ans[i];
				
				flag=0;
				}
				cout<<endl;
			}
		
				
			if(ans[0]==ans[2]&&ans[2]==ans[5]&&ans[5]==ans[7]&&ans[1]==ans[3]&&ans[3]==ans[4]&&ans[4]==ans[6]){
			
				for(int i=0;i<8;i++){
				cout<<ans[i];
				}	
				cout<<endl;
				break;
			}
			
				
		}	
		m++;
	}
		
	return 0;
}

试题H:子串分值和

时间限制: 1.0s内存限制: 256.0MB本题总分:20分

【问题描述】

​ 对于一个字符串s,我们定义S的分值 f(S)为S中出现的不同的字符个数。例如f("aba") = 2,f("abc") = 3,f("aaa") = 1。
​ 现在给定一个字符串 S 0..n-1,请你计算对于所有S的非空子串S[i..j](0 ≤i≤ j<n),f(S[i..j])的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串s。

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

28

【样例说明】

子串 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

【评测用例规模与约定】

对于20%的评测用例,1≤n≤ 10;

对于40%的评测用例,1≤n ≤100;

对于50%的评测用例,1≤n ≤ 1000;

对于60%的评测用例,1≤n ≤ 10000;

对于所有评测用例,1≤n ≤ 100000。

  • 暴力解法 至少能过五个数据
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
string s;
ll ans;
void slove(int a,int b){
	int f[26];
	memset(f,0,sizeof(f));
	for(int i=a;i<=b;i++){
		f[s[i]-'a']++;
	}
	for(int i=0;i<=25;i++){
		if(f[i]){
			ans++;
		}
	}
}


int main() {
	cin>>s;
	int n=s.size();
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++){
			slove(i,j); 
		}
		
	cout<<ans;
	
    return 0;
    
}
  • 常规解法
不会

试题I:平面切分

时间限制: 1.0s内存限制: 256.0MB本题总分:25分

【问题描述】

​ 平面上有N条直线,其中第i条直线是y =Aj·x+B。

​ 请计算这些直线将平面分成了几个部分。

【输入格式】

​ 第一行包含一个整数N。
​ 以下N行,每行包含两个整数A,B;。

【输出格式】

​ 一个整数代表答案。

【样例输入】

​ 3
​ 1 1

​ 2 2

​ 3 3

【样例输出】

​ 6

【评测用例规模与约定】

​ 对于50%的评测用例,1≤N≤4,-10 ≤A,B; ≤ 10。
​ 对于所有评测用例,1≤N ≤1000,-100000≤A;,Bi≤100000。

不会(特判骗分

试题J:字串排序

时间限制: 1.0s内存限制: 256.0MB本题总分:25分

【问题描述】

​ 小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。

​ 在冒泡排序中,每次只能交换相邻的两个元素。
​ 小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个字符,则在所有可能的排序方案中,冒泡排序的总交换次数是最少的。
​ 例如,对于字符串lan排序,只需要1次交换。对于字符串qiao排序,总共需要4次交换。
​ 小蓝的幸运数字是V,他想找到一个只包含小写英文字母的字符串,对这个串中的字符进行冒泡排序,正好需要Ⅳ次交换。请帮助小蓝找一个这样的字符串。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

【输入格式】

​ 输入一行包含一个整数v,为小蓝的幸运数字。

【输出格式】

​ 输出一个字符串,为所求的答案。

【样例输入】

​ 4

【样例输出】

​ bbaa

【样例输入】

​ 100

【样例输出】

​ jihgfeeddccbbaa

【评测用例规模与约定】

​ 对于30%的评测用例,1≤v≤ 20。

​ 对于50%的评测用例,1≤v ≤ 100。

​ 对于所有评测用例,1≤V ≤ 10000。

不会

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×