第十一届蓝桥杯C++B组省赛第二场练习记录 - Cache One

试题 A: 门牌制作

答案:624

思路模拟

代码:

/*
624
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

//有几个2 
int calc(int num) {
	int t = num;
	int res = 0;
	//取每位数字 
	while(t) {
		int x = t%10;
		if(x==2) res++;
		t/=10;
	}
	return res;
}

int main() {
	int sum = 0;
	for(int i = 1; i <= 2020; i++) {
		sum += calc(i);
	}
	cout << sum << endl;
	return 0;
}

试题 B: 既约分数

答案:2481215

思路:模拟

代码:

/*
2481215
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

//gcd模板 
int gcd(int a,int b) {
	return b?gcd(b,a%b):a;
}

int main() {
	int ans = 0;
	for(int i = 1; i <= 2020; i++)
		for(int j = 1; j <= 2020; j++)
			if(gcd(i,j)==1) ans++;
	cout << ans << endl;
	return 0;
}

试题 C: 蛇形填数

答案:761

思路:模拟,分成4个状态来走。

状态1:向右走1格,切状态
状态2:方向左下走,到第1列切状态
状态3:向下走1格,切状态
状态4: 向右上走,到第1行切状态(回1)

代码:

/*
761
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200; 	//多开一点,防止出错
int a[N][N];

int main() {
	int cnt = 1;	//计数 
	int i = 1, j = 1;
	int mode = 1;
	a[i][j] = cnt++;	//初始d
	while(i<=20 || j<=20) {
		switch(mode) {
			case 1:
				j+=1;
				a[i][j] = cnt++;
				mode++;
				break;
			case 2:
				i+=1;
				j-=1;
				a[i][j] = cnt++;
				if(j==1) mode++;
				break;
			case 3:
				i+=1;
				a[i][j] = cnt++;
				mode++;
				break;
			case 4:
				i-=1;
				j+=1;
				a[i][j] = cnt++;
				if(i==1) mode = 1;
				break;
		}
		
	}
	//输出矩阵 
	for(int i = 1; i<= 20; i++) {
		for(int j = 1; j <= 20; j++) {
			printf("%4d ",a[i][j]);
		}
		cout << endl;
	}
	
	//输出答案 
	cout << "\n" << a[20][20] << endl;
	
	return 0;
}

试题 D: 跑步锻炼

答案:8879

思路:模拟,日期检查模板要熟记(判月、润2处理,判日)

代码:

/*
8879
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

//日期检查模板
const int table[13] = {
	0,31,28,31,30,31,30,31,31,30,31,30,31,
};
bool check(int year,int mon,int day) {
	//判月 
	if(mon<1 || mon > 12) return false;
	int leap = 0;
	//润2处理 
	if(mon==2)
		if(year%4==0 && year%100!=0 || year%400==0) leap++;
	//判日
	if(day<1 || day > table[mon]+leap) return false;
	
	return true;
}

int main() {
	int ans = 0;
	int xq = 6;
	//可以从20000101遍历到20201001
	for(int i = 20000101; i <= 20201001; i++) {
		int y = i/10000;
		int m = i/100%100;
		int d = i%100;
		if(check(y,m,d)) {
			if(xq==1||d==1) ans+=2;
			else ans+=1;
			
			xq++;
			if(xq==8)xq=1;
		}
	}
	cout << ans << endl;
	return 0;
}

试题 E: 七段码

答案:80

思路:并查集或者用dfs,bfs看图的连通性。

并查集代码:

/*
80
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int a[7], p[7];
int e[7][7] = {	//邻接矩阵 
	1,1,0,0,0,1,0,
	1,1,1,0,0,0,1,
	0,1,1,1,0,0,1,
	0,0,1,1,1,0,0,
	0,0,0,1,1,1,1,
	1,0,0,0,1,1,1,
	0,1,1,0,1,1,1,
};

int find(int x) {
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main() {
	int ans = 0;
	
	for(int i = 0 ; i <= 127; i++) {	//二进制遍历

		//初始化并查集,记录亮灯情况 
		for(int j = 0; j < 7; j++) p[j] = j, a[j] = i >> j & 1;
		
		//如果亮灯且相连,合并集合
		for(int j = 0; j < 7; j++)
			for(int k = 0; k < 7; k++)
				if(a[j] && a[k] && e[j][k]) p[find(j)] = find(k); 
					
		int cnt = 0;	//看亮灯的有几个自己是老祖宗的 
		for(int j = 0; j < 7; j++) if(a[j] && j == p[j]) cnt++;
			
		//如果只有1个老大,那么亮灯的都在一个集合中 
		if(cnt == 1) ans++;
	}
	cout << ans << endl;
	
	return 0;
}

BFS代码:

/*
80
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int a[7];
int lj[7][7] = {
	1,1,0,0,0,1,0,
	1,1,1,0,0,0,1,
	0,1,1,1,0,0,1,
	0,0,1,1,1,0,0,
	0,0,0,1,1,1,1,
	1,0,0,0,1,1,1,
	0,1,1,0,1,1,1, 
};
bool st[7];

void bfs(int start) {
	queue<int> q;
	memset(st,0,sizeof st);
	
	st[start]=true;
	q.push(start);
	
	while(q.size()) {
		int cur = q.front();
		q.pop();
		for(int i = 0; i < 7; i++) {
			if(!a[i]) continue;	//不亮灯跳出 
			if(!lj[cur][i]) continue;	//不连接跳出 
			if(st[i]) continue;	//走过跳出 
			
			st[i] = true;
			q.push(i);
		}
	}
}

int main() {
	int ans = 0;
	for(int i = 0 ; i <= 127; i++) {
		int tar = 0;	//亮灯的个数 
		for(int j = 0; j < 7; j++) {
			a[j] = i>>j&1;
			if(a[j]) tar++;
		}
		//得到一种表达,判断连通性
		for(int j = 0; j < 7; j++) {
			if(a[j]) {	//找到其中一个亮灯的点 
				bfs(j);	//开始扩展,将该点能扩展的都走一遍 
				int num = 0;	//联通的个数 
				for(int k = 0; k < 7; k++) {
					if(st[k]) num++;
				}
				if(num == tar) ans++;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

试题 F: 成绩统计

思路:简单计算

代码:

/*
及格率 = 及格人数/总人数
优秀率同理
7
80
92
56
74
88
100
0

*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
int a[N];

int main() {
	int n;	//考试人数
	cin >> n;
	int jg = 0, yx = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		if(a[i]>=60) jg++;
		if(a[i]>=85) yx++;
	}
	double jgl = (double)jg/n * 100.0;
	double yxl = (double)yx/n * 100.0;
	printf("%.0llf\%\n",jgl);
	printf("%.0llf\%\n",yxl);
	return 0;
}

试题 G: 回文日期

思路:

遍历所有回文
4个数的全排列(带start)
找到第一个就返回

遍历所有ababbaba
2个数的全排列
找到第一个就返回

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

char a[10];

//日期检查模板
const int table[13] = {
	0,31,28,31,30,31,30,31,31,30,31,30,31,
};
bool check(int year,int mon,int day) {
	//判年
	if(year<1 || year>9999) return false; 
	//判月 
	if(mon<1 || mon > 12) return false;
	int leap = 0;
	//润2处理 
	if(mon==2)
		if(year%4==0 && year%100!=0 || year%400==0) leap++;
	//判日
	if(day<1 || day > table[mon]+leap) return false;
	
	return true;
}

int main() {
	cin >> a;
	for(int i = 0; i < 8; i++) a[i] = a[i] - '0';
	int cy = a[0]*1000+a[1]*100+a[2]*10+a[3];
	int cm = a[4]*10+a[5];
	int cd = a[6]*10+a[7];
	int cur = cy*10000+cm*100+cd;
	
	bool flag = false;
	for(int i = 0; i <= 9; i++) {
		for(int j = 0; j <= 9; j++) {
			for(int k = 0; k <= 9; k++) {
				for(int l = 0; l <= 9; l++) {
					int y = i*1000+j*100+k*10+l;
					int m = l*10+k;
					int d = j*10+i;
					if(check(y,m,d)) {
						int num = y*10000+m*100+d;
						if(num>cur) {
							printf("%d%02d%02d\n",y,m,d);
							flag = true;
							break;
						}
					}
				}
				if(flag)break; 
			}
			if(flag)break; 
		}
		if(flag)break; 
	}
	
	flag = false;
	for(int i = 0; i <= 9; i++) {
		for(int j = 0; j <= 9; j++) {
			int y = i*1000+j*100+i*10+j;
			int m = j*10+i;
			int d = j*10+i;
			if(check(y,m,d)) {
				int num = y*10000+m*100+d;
				if(num>cur) {
					printf("%d%02d%02d\n",y,m,d);
					flag = true;
					break;
				}
			}
		}
		if(flag)break; 
	}
	return 0;
}

试题 H: 子串分值和

思路:骗分,遍历左右,得到全部子串,算所有f(子串)的和

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int N = 100010;
char a[N],b[N];
bool st[130];

int f(char b[]) {
	int ans = 0;
	int len = strlen(b);
	memset(st,0,sizeof st);
	
	for(int i = 0; i < len; i++) st[b[i]] = true;
	for(int i = 0; i < 130; i++) if(st[i])ans++;
	
	return ans;
}

int main() {
	cin >> a;
	int len = strlen(a);
	int sum = 0;
	for(int l = 0; l < len; l++) {
		for(int r = l; r < len; r++) {
			strncpy(b,a+l,r-l+1);
			b[r-l+1]=0;
			//cout << b << "\t" << f(b) << endl;
			sum += f(b);
		}
	}
	cout << sum << endl;
	return 0;
}

试题 I: 平面切分

没做。

试题 J: 字串排序

没做。

为您推荐