2020第十一届蓝桥杯C++省赛B组真题和题解（10月第二场）

试题A:门牌制作

题目

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

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

题解

答案：624

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
const int INF = 1e9;
int cnt;
void cal(int x){
	while(x){
		if(x % 10 == 2) cnt++;
		x /= 10;
	}
}
int main(){
	for(int i = 1; i <= 2020; i++){
		cal(i);
	}
	cout << cnt;
	return 0;
}

试题B:既约分数

题目

【问题描述】如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。例如，3/4,5/2,1/8,7/1都是既约分数。请问，有多少个既约分数，分子和分母都是1到2020之间的整数（包括1和2020）？
【答案提交】这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

答案：2481215

注：gcd()为求最大公约数函数

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
const int INF = 1e9;
const int MAX = 2020;
int x, y;
int gcd(int a, int b){
	return !b ? a : gcd(b, a % b);
}
int main(){
	int cnt = 0;
	for(int i = 1; i <= MAX; i++){
		for(int j = 1; j <= MAX; j++){
			if(gcd(i, j) == 1) {
				cnt++;
			}
		}
	}
	cout << cnt;
	return 0;
}

试题C:蛇形填数

题目

【问题描述】
如下图所示，小明用从1开始的正整数“蛇形”填充无限大的矩阵。容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少？

在这里插入图片描述
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

找规律题
答案：761

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
const int INF = 1e9;
int x;
int cal(int n){
	return 2*n*n - 2 * n + 1;
}
int main(){
	while(cin >> x){
		cout << cal(x) << endl;	
	}
	return 0;
}

试题D:跑步锻炼

题目

【问题描述】小蓝每天都锻炼身体。正常情况下，小蓝每天跑1千米。如果某天是周一或者月初（1日），为了激励自己，小蓝要跑2千米。如果同时是周一或月初，小蓝也是跑2千米。小蓝跑步已经坚持了很长时间，从2000年1月1日周六（含）到2020年10月1日周四（含）。请问这段时间小蓝总共跑步多少千米？
【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

答案：8879

可以用excel做
额外多跑1km的天数：1299
7580 + 1299 = 8879天

试题F:成绩统计

题目

【问题描述】
小蓝给学生们组织了一场考试，卷面总分为100分，每个学生的得分都是一个0到100的整数。如果得分至少是60分，则称为及格。如果得分至少为85分，则称为优秀。请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。
【输入格式】
输入的第一行包含一个整数n，表示考试人数。接下来n行，每行包含一个0至100的整数，表示一个学生的得分。
【输出格式】
输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分四舍五入保留整数。
【样例输入】
780925674881000
【样例输出】
71%
43%
【评测用例规模与约定】
对于50%的评测用例，1<=n<=100。对于所有评测用例，1<=n<=10000。

题解

使用round()完成四舍五入操作

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
const int INF = 1e9;
int n;
int cnt1 = 0;
int cnt2 = 0;
int main(){
	scanf("%d", &n);
	int N = n;
	int x;
	while(N--){
		cin >> x;
		if(x >= 60) cnt1++;
		if(x >= 85) cnt2++;
	}
	cout << round(cnt1*1.0 / n * 100) << "%" << endl;
	cout << round(cnt2*1.0 / n * 100) << "%";
	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 <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;
const int INF = 1e9;
const int maxn = 8;
int x;
int str[maxn];
int cnt;

//闰年：能被4整除但不能被100整除,或能被400整除的
int leap_year[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int nonleap_year[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

void convert(int x){
	cnt = 0;
	while(x){
		str[7-cnt++] = x % 10;
		x /= 10;
	}
}
bool jg_leap_year(int y){
    return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}
int next_day(int x){
	int y = x / 10000;  //取前四位
	int m = x % 10000 / 100; //取最后四位的前两位
	int d = x % 100;  //取最后两位
    if(d++ == (jg_leap_year(y)? leap_year[m - 1] : nonleap_year[m - 1])){
        d = 1;
        if(m++ == 12){
            y++;
            m = 1;
        }
    }
    return y * 10000 + m * 100 + d;
}

//判断是否为回文
bool jg1(int x){
	convert(x);
	for(int i = 0; i <= 3; i++){
		if(str[i] != str[7 - i]) return false;
	}
	return true;
}
//判断是否为ABABBABA型回文
bool jg2(int x){
	//首先判断是否为回文
	if(jg1(x) == false) return false;
	return (str[0] != str[1] && str[0] == str[2] && str[1] == str[3]);
}
int main(){
	cin >> x;
	int y1 = x;

	while(y1 = next_day(y1)){
		if(jg1(y1)){
			cout << y1 << endl;
			break;
		}
	}
	int y2 = x;
	while(y2 = next_day(y2)){
		if(jg2(y2)){
			cout << y2 ;
			break;
		}
	}
	return 0;
}

试题H:子串分值和

题目

时间限制: 1.0s
内存限制: 256.0MB
本题总分：20分
在这里插入图片描述

题解

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <iostream>
using namespace std;
const int INF = 1e9;
string s;
int ans;
int cal(string s){
	set<char> st; 
	for(int i = 0; i < s.size(); i++){
		st.insert(s[i]);
	}
	return st.size();
}
int main(){
	cin >> s;
	for(int i = 0; i < s.size(); i++){
		for(int j = i; j < s.size(); j++){
			string ss = s.substr(i, j - i + 1);
			ans += cal(ss);
		}
	}
	cout << ans;
	return 0;
}

试题I:平面切分

题目

【问题描述】
平面上有N 条直线，其中第 $i$ 条直线是 $y = A_i x + B_i$ 。
请计算这些直线将平面分成了几个部分。
【输入格式】
第一行包含一个整数N。
以下N 行，每行包含两个整数 $A_i$ ; $B_i$ 。
【输出格式】
一个整数代表答案。
【样例输入】
3 1
1
2 2
3 3
【样例输出】
6
【评测用例规模与约定】
对于50% 的评测用例，1 <= $N$ <= 4, -10 <= $A_i, B_i$ <= 10。
对于所有评测用例，1 <= N <= 1000, 100000 <= Ai; Bi <= 100000。

题解

用了递推的思想，算不上动态规划。
第一条直线把直线分成2部分；
第二条直线与现有直线可以有1）0个交点 2）1个交点

两条直线求交点函数 cal_CrossPoint() 求出交点坐标
第n条直线与已有区域有 cp_num 个交点，则多分（新增）出 cp_num+1 个部分
则所求总区域数更新 ans += cp_num + 1;

/*
可以尝试 不用vector 用set 自动判重（可能需要重新改写hash）来进一步优化时间复杂度 
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1005;
const int INF = 1e9;
int N; 
int a[maxn], b[maxn];
struct nd{
	double x, y;
};
bool jg_equal(nd e1, nd e2){
	//注意浮点数相等的比较 
	return (abs(e1.x - e2.x) < 1e-2 && abs(e1.y - e2.y) < 1e-2);
}
nd cal_CrossPoint(int m, int n){ //计算并返回第m , n条直线的交点 
	double a1 = a[m], a2 = a[n], b1 = b[m], b2 = b[n];
	//两直线平行，等价于交点在无穷远处 
	if(a1 == a2) return nd{INF, INF};
	nd cp = nd{};
	cp.x = (b2 - b1)/(a1 - a2);
	cp.y = (a1*b2 - a2 * b1) / (a1 - a2);  
	return cp;	
}
int main(){
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> a[i] >> b[i];
	}
	int ans = 2; //所求总区域数，初始值为n=1, 分为2个区域 
	for(int i = 2; i <= N; i++){
		vector<nd> s;  
		for(int j = 1; j < i; j++){
			nd now = cal_CrossPoint(i, j);
			bool fg = false;
			if(now.x == INF || now.y == INF){
				continue;
			}
			for(int k = 0; k < s.size(); k++){
				if(jg_equal(now, s[k])) fg = true;
			}
			if(!fg) s.push_back(now);		
		}
		int cp_num = s.size();
		ans += cp_num + 1;
	} 
	cout << ans << endl;
	return 0;
}

未完待续…

原文链接：https://blog.csdn.net/Cinnamon_Roll/article/details/109138791

目录