2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
真题
第一题：门牌制作
题目描述
小蓝要为一条街的住户制作门牌号。这条街一共有2020位住户，门牌号从1到2020编号。小蓝制作门牌的方法是先制作0到9这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌1017需要依次粘贴字符1、0、1、7，即需要1个字符0，2个字符1，1个字符7。请问要制作所有的1到2020号门牌，总共需要多少个字符2？
第二题：既约分数
题目描述
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。例如，3/4,5/2,1/8,7/1都是既约分数。请问，有多少个既约分数，分子和分母都是1到2020之间的整数（包括1和2020）
第三题：蛇形填数
题目描述
如下图所示，小明用从1开始的正整数“蛇形”填充无限大的矩阵。容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少？
1 2 6 7 15 …
3 5 8 14 …
4 9 13 …
10 12 …
11 …
第四题：跑步锻炼
题目描述
小蓝每天都锻炼身体。正常情况下，小蓝每天跑1千米。如果某天是周一或者月初（1日），为了激励自己，小蓝要跑2千米。如果同时是周一或月初，小蓝也是跑2千米。小蓝跑步已经坚持了很长时间，从2000年1月1日周六（含）到2020年10月1日周四（含）。请问这段时间小蓝总共跑步多少千米？
第五题：七段码
题目描述
小蓝要用七段码数码管来表示一种特殊的文字。
七段码上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
第六题：成绩统计
题目描述
小蓝给学生们组织了一场考试，卷面总分为100分，每个学生的得分都是一个0到100的整数。如果得分至少是60分，则称为及格。如果得分至少为85分，则称为优秀。请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。
【输入格式】 输入的第一行包含一个整数n，表示考试人数。接下来n行，每行包含一个0至100的整数，表示一个学生的得分。
【输出格式】 输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分四舍五入保留整数。
【样例输入】
7
80
92
56
74
88
100
0
【样例输出】
71%
43%
第七题：回文日期
题目描述
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位数表示。
第八题：子串分值和
题目描述
对于一个字符串 S，我们定义 S 的分值 f (S ) 为 S 中出现的不同的字符个
数。例如 f (”aba”) = 2， f (”abc”) = 3, f (”aaa”) = 1。
现在给定一个字符串 S [0::n − 1]（长度为 n），请你计算对于所有 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
第九题：平面切分
题目描述
平面上有N 条直线，其中第i条直线是y = Ai x+Bi
请计算这些直线将平面分成了几个部分。
【输入格式】
输入的第一行包含一个整数N, 以下N行，包含两个证书 Ai，Bi
【输出格式】 一个整数代表答案
【样例输入】
3 1
1
2 2
3 3
【样例输出】
6
第十题：字串排序
题目描述
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。
【输入格式】
输入的第一行包含一个整数V。
【输出格式】
题面要求的一行字符串。
【样例输入】
4
【样例输出】
bbaa
【样例输入】
100
【样例输出】
jihgfeeddccbbaa
题解
第一题：门牌制作
分析
枚举
代码
#include<iostream>
using namespace std;
typedef long long ll;
int twonum(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+=twonum(i);
}
cout<<ans<<endl;
return 0;
}
ans： 624
第二题：既约分数
分析
枚举
最大公约数可以用gcd去求
代码
#include<iostream>
using namespace std;
typedef long long ll;
bool isok(int a,int b){
if(a>b){
int t=a;
a=b;
b=t;
}
int i;
for(i=a;i>=1;i--){
if(a%i==0&&b%i==0)break;
}
if(i==1)return true;
return false;
}
int main(){
int ans=0;
for(int i=1;i<=2020;i++){
for(int j=1;j<=2020;j++){
if(isok(i,j)){
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
ans： 2481215
第三题：蛇形填数
分析
模拟
代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int main(){
int i=1;
int t=1;
while(1){
int sum=0;
for(int j=0;j<t;j++){
sum+=i;
i++;
}
if(20*2-1==t){
cout<<sum/t<<endl;
break;
}
t++;
}
return 0;
}
ans 761
第四题：跑步锻炼
分析
经典日期题
代码
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
int y=2000,m=1,d=1;
int ms[]={31,28,31,30,31,30,31,31,30,31,30,31};
int x=6;
int ans=0;
while(!(y==2020&&m==10&&d==1)){
ans++;
if(d==1||x==1)ans++;
if((y%100!=0&&y%4==0)||y%400==0)ms[1]=29;
else ms[1]=28;
d++;
if(d==ms[m-1]+1){
m++;
d=1;
if(m==13){
m=1;
y++;
}
}
x=(x+1)%7;
}
ans+=2;
cout<<ans<<endl;
return 0;
}
ans 8879
第五题：七段码
分析
dfs+查重
这里用的查重方式是用小于等于八位的数字来表示一个状态，其中每一位有1和0两种情况，1表示选择对应二极管，0表示不选择。最后只需将int放入set中即可排重。
代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
set<int> ans;
void dfs(vector<vector<int>> &a,vector<int> &sign,int c){
//这里的查重方式不如位运算，但是也足够了。
int t=0;
for(int i=1;i<=7;i++){
t*=10;
if(sign[i]==0){
t+=i;
}
}
ans.insert(t);
int n=a[c].size();
for(int i=0;i!=n;i++){
if(sign[a[c][i]]){
sign[a[c][i]]=0;
dfs(a,sign,a[c][i]);
sign[a[c][i]]=1;
}
}
}
int main()
{
vector<int> sign(8,1);
vector<vector<int>> a(8,vector<int>());
//每个二极管相邻的二极管编号，1234567对应abcdefg
a[0]=vector<int>{1,2,3,4,5,6,7};
a[1]=vector<int>{2,6};
a[2]=vector<int>{1,3,7};
a[3]=vector<int>{2,7,4};
a[4]=vector<int>{3,5};
a[5]=vector<int>{4,6,7};
a[6]=vector<int>{1,5,7};
a[7]=vector<int>{2,3,5,6};
dfs(a,sign,0);
//会多一个什么都没选的，如果不想多这一个也可以遍历每一个节点，让每个节点为头节点
cout<<ans.size() - 1<<endl;
return 0;
}
ans 80
第六题：成绩统计
分析
模拟四舍五入过程
c++是向下取整，题目要求四舍五入，直接保留%前两位可能会有误差。
代码
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
int main()
{
int jnum=0,ynum=0;
int n;
cin>>n;
for(int i=0;i!=n;i++){
int t;
cin>>t;
if(t>=60)jnum++;
if(t>=85)ynum++;
}
float jans=(float)jnum/n;
float yans=(float)ynum/n;
jans*=1000;
yans*=1000;
cout<<(int)jans/10+(((int)jans%10)>4?1:0)<<"%"<<endl;
cout<<(int)yans/10+(((int)yans%10)>4?1:0)<<"%"<<endl;
return 0;
}
第七题：回文日期
分析
直接用八位数遍历时间应该有点紧张，这里用的是年份（4位数）遍历，直接构造回文数，判断是否位合法日期
细节的 用bool记录第一个回文数的输出情况，输出之后不再输出并且找到abab可以break
代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
void pr(int y,int m,int d){
cout<<y;
if(m<10)cout<<"0";
cout<<m;
if(d<10)cout<<"0";
cout<<d;
cout<<endl;
}
int main()
{
string init;
cin>>init;
int iny=(init[0]-'0')*1000+(init[1]-'0')*100+(init[2]-'0')*10+(init[3]-'0');
int inm=(init[4]-'0')*10+(init[5]-'0');
int ind=(init[6]-'0')*10+(init[7]-'0');
int mms[12]={31,28,31,30,31,30,31,31,30,31,30,31};
bool sign=true;
for(int i=iny;i<10000;i++){
int t=i;
int arr[4];
for(int j=0;j!=4;j++){
arr[j]=t%10;
t/=10;
}
int mm=arr[0]*10+arr[1];
int dd=arr[2]*10+arr[3];
if((i%4==0&&i%100!=0)||(i%400==0)){
mms[1]=29;
}else{
mms[1]=28;
}
if(mm>12||mm<1)continue;
if(dd>mms[mm-1]||dd<1)continue;
if(sign){
if(i==iny){
if(mm>inm||(mm==inm&&dd>ind)){
pr(i,mm,dd);
sign=false;
}
}else{
pr(i,mm,dd);
sign=false;
}
}
if((!sign)&&(i%100==i/100)){
pr(i,mm,dd);
break;
}
}
return 0;
}
第八题：子串分值和
分析
每个字母只有在第一次出现时才有贡献度，所以我们只需统计每个字母在第一次出现的情况下，能被多少子串所包含。
用一个数组sign[26]去记录字符str[i] 上一次出现的位置，就可以求出str[i]字符在多少个子串中为第一次出现的，计算方法为(i-sign[w])*(n-i)；
举例解释：abcadc
假设我们遍历到第二个a
这时我们要求第二个a为子串第一次出现a的子串的个数：
（第二个a的下标 - 第一个a的下标）* 后面的个数
abcabc（黄色的个数）* abcabc（黄色个数）= 3 * 2
abcabc
abcabc
abcabc
abcabc
abcabc
abcabc
abcabc
abcabc
abcabc
代码
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int main(){
string str;
cin>>str;
ll n=str.size();
vector<int> sign(26,-1);
ll ans=0;
for(int i=0;i<n;i++){
int w=str[i]-'a';
ans+=(i-sign[w])*(n-i);
sign[w]=i;
}
cout<<ans<<endl;
return 0;
}
第九题：平面切分
分析
核心思路就是每增加一条线，就判断他和之前的线的关系，多一个交点，则多一个面，需要注意的是交点可能重复
不清楚可以多画图
代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
int main(){
int N;
cin>>N;
set<pair<double,double>> s;
for(int i=0;i!=N;i++){
int a,b;
cin>>a>>b;
s.insert({a,b});
}
vector<pair<double,double>> ls;
for(auto t:s){
ls.push_back(t);
}
ll ans=1;
int n=ls.size();
for(int i=0;i<n;i++){
//计算交点个数
set<pair<double,double>> tempjds;
for(int j=0;j<i;j++){
if(ls[j].first==ls[i].first)continue;
double x=(ls[j].second-ls[i].second)/(ls[i].first-ls[j].first);
double y=ls[i].first*x+ls[i].second;
tempjds.insert({x,y});
}
ans+=tempjds.size()+1;
}
cout<<ans<<endl;
return 0;
}
第十题：字串排序
分析
找一个只包含小写英文字母且没有字母重复出现的字符串&&请注意字符串中可以包含相同的字符
自行理解
下面是没有字母重复出现的题解
int main()
{
int v;
cin>>v;
vector<int> arr(26+1);
for(int i=2;i<=26;i++){
arr[i]=arr[i-1]+i-1;
}
int len;
for(int i = 26;i>=1;i--){
if(v>arr[i]){
len=i + 1;
break;
}
}
int temp=v-arr[len-1];
vector<int> ans;
for(int i=len-1;i>0;i--){
if(i==temp){
ans.push_back(len);
}
ans.push_back(i);
}
string strans;
for(auto a:ans)strans+=a-1+'a';
cout<<strans<<endl;
return 0;
}