2020蓝桥杯省赛B组部分题解
A题 门牌制作
【问题描述】
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字
符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、 0、 1、 7，即需要 1 个
字符 0， 2 个字符 1， 1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2 ？
【解题思路】
一道简单题。模拟1～2020，用四个字母记录每位上的数字，如果是2，sum++即可。
【代码实现】
#include <iostream>
using namespace std;
int main(){
int g,s,b,q,sum=0;
for (int i=1; i<=2020; i++) {
g=i%10;
s=(i/10)%10;
b=(i/100)%10;
q=(i/1000)%10;
if (g==2) {
sum++;
}
if (s==2) {
sum++;
}
if (b==2) {
sum++;
}
if (q==2) {
sum++;
}
}
cout<<sum<<endl;
}
答案：624。
B题 既约分数
【问题描述】
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。例如，3/4 , 5/2 , 1/8 , 7/1都是既约分数。请问，有多少个既约分数，分子和分母都是1 到2020 之间的整数（包括1和2020）？
【解题思路】
写一个子函数计算两个数的公约数，如果找到大于1的公约数，则return false。主函数用两个for循环遍历所有分子分母的可能（注意：分子可以大于分母
【代码实现】
#include<iostream>
using namespace std;
int minn(int x,int y){
if(x>y){
return y;
}else{
return x;
}
}
bool gongyueshu(int x,int y){
if(x==1||y==1){
return true;
}
for(int i=2;i<=minn(x,y);i++){
if(x%i==0&&y%i==0){
return false;
}
}
return true;
}
int main(){
int i,j;
int num=0;
for(i=1;i<=2020;i++){
for(j=1;j<=2020;j++){
if(gongyueshu(i,j)){
num++;
}
}
}
cout<<num<<endl;
}
答案：2481215。
C题 蛇形填数
【问题描述】
如下图所示，小明用从1 开始的正整数“蛇形”填充无限大的矩阵。
容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少？
【解题思路】
可以写代码模拟过程。更简单的方法是利用填数规则找规律，对于第n行n列的数x，x一定在第2n-1斜列（第1斜列有一个数为1，第2斜列有两个数为2、3，… ，第n斜列有n个数），
那么先计算前2n-2斜列一共有多少数（等差数列求和），
再加上x所在斜列前面有多少数（观察可知，数字5在第3斜列的第2个，数字13在第5斜列的第3个，… ，数字x在第2n-1斜列的第n个）。
答案：761。
D题 跑步锻炼
【问题描述】
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了
激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。
小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年
10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
【解题思路】
显然可以用代码从2000-01-01模拟至2020-10-01，需要注意闰年的判断。
但对于这种日期题，最好的方法是excel，如下图。
利用excel的日期相减功能，计算出期间有多少天，从而计算出有多少个星期一。
再利用excel筛选功能，找出有多少个1号的周一，从而便能计算出结果。
答案：8879。
E题 七段码
【问题描述】
小蓝要用七段码数码管来表示一种特殊的文字。
七段码上图给出了七段码数码管的一个图示，数码管中一共有7 段可以发光的二极管，分别标记为a, b, c, d, e, f, g。小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
【解题思路】
拿到题时，第一反应是深度优先搜索（dfs）。深搜大部分是用在树型数据，而此题是一道图论。无论搜索哪个，深搜的最深点一定是7个灯全点亮。所以这就衍生出如何去重这一问题。
答主所采用的去重方法是：先把a～g用1-7表示。对于每次深搜的结果，例如abgcd点亮，其所对应的数字为12347（数字升序排序），若ans[12347]=0则ans[12347]=1，且sum++。
【代码实现】
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int book[8][8];
int bookk[10];
int ans[9999999];
int sum=0;
void dfs(int x){
int i,k,n,p;
for(i=1;i<=7;i++){
if(bookk[i]==0&&book[x][i]==1){
bookk[i]=1;
n=0;
p=0;
for(k=7;k>=1;k--){
if(bookk[k]==1){
p+=k*pow(10,n);
n++;
}
}
if(ans[p]==0){
ans[p]=1;
sum++;
//cout<<p<<endl;
}
dfs(i);
bookk[i]=0;
}
}
}
int main(){
memset(book,0,sizeof(book));
memset(bookk,0,sizeof(bookk));
book[1][2]=1;
book[1][6]=1;
book[2][1]=1;
book[2][7]=1;
book[2][3]=1;
book[3][4]=1;
book[3][2]=1;
book[3][7]=1;
book[4][3]=1;
book[4][5]=1;
book[5][4]=1;
book[5][6]=1;
book[5][7]=1;
book[6][1]=1;
book[6][5]=1;
book[6][7]=1;
book[7][2]=1;
book[7][3]=1;
book[7][5]=1;
book[7][6]=1;
for (int i=1; i<=7; i++) {
bookk[i]=1;
sum++;
dfs(i);
bookk[i]=0;
}
cout<<sum<<endl;
}
答案：80。
F题 成绩统计
【问题描述】
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是
一个 0 到 100 的整数。
如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。
请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整
数。
【解题思路】
一道简单题。用a、b记录及格优秀人数，每次输入数据时，判断。最后计算百分率，注意四舍五入。
【代码实现】
#include <iostream>
#include<iostream>
using namespace std;
int main(){
int n,a=0,b=0,x;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(x>=60){
a++;
}
if(x>=85){
b++;
}
}
if(((a*100)%n)*10<n*5){
cout<<a*100/n;
}else{
cout<<a*100/n+1;
}
cout<<'%'<<endl;
if(((b*100)%n)*10<n*5){
cout<<b*100/n;
}else{
cout<<b*100/n+1;
}
cout<<'%'<<endl;
return 0;
}
G题 回文日期
【问题描述】
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202，
恰好是一个回文数。我们称这样的日期是回文日期。
有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202 即2021年12月2日。
也有人表示20200202 并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。
给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天
【解题思路】
一开始的想法是暴力计算，无限循环，每次将日期++，然后判断是否回文，是否合法日期（注意闰年）。然后运行时目测时间爆了。进行优化，每次将年份++，然后将整体变为回文，判断是否合法日期。ABABBABA式回文同理。
【代码实现】
#include<iostream>
using namespace std;
char a[9];
int yy,mm,dd;
bool legal(){
int y=(a[1]-'0')*1000+(a[2]-'0')*100+(a[3]-'0')*10+(a[4]-'0');
if(y<=yy){
return false;
}
int m=(a[5]-'0')*10+(a[6]-'0');
if(y==yy&&m<=mm){
return false;
}
int d=(a[7]-'0')*10+(a[8]-'0');
if(y==yy&&m==mm&&d<=dd){
return false;
}
if(m==1||m==3||m==5||m==7||m==8||m==10||m==12){
if(d<=31){
return true;
}
}
if(m==4||m==6||m==9||m==11){
if(d<=30){
return true;
}
}
if(y%400==0||(y%4==0&&y%100!=0)){
if(m==2){
if(d<=29){
return true;
}
}
}else{
if(m==2){
if(d<=28){
return true;
}
}
}
return false;
}
void outt(){
for(int i=1;i<=8;i++){
cout<<a[i];
}
cout<<endl;
}
int main(){
int i;
a[0]='0';
for(i=1;i<=8;i++){
cin>>a[i];
}
yy=(a[1]-'0')*1000+(a[2]-'0')*100+(a[3]-'0')*10+(a[4]-'0');
mm=(a[5]-'0')*10+(a[6]-'0');
dd=(a[7]-'0')*10+(a[8]-'0');
for(i=1;;){
for(;i<=4;i++){
a[9-i]=a[i];
}
if(legal()){
outt();
break;
}
for(i=4;i>=1;i--){
if(a[i]=='9'){
a[i]='0';
}else{
a[i]+=1;
break;
}
}
}
for(i=1;;){
a[3]=a[1];
a[6]=a[1];
a[8]=a[1];
a[4]=a[2];
a[5]=a[2];
a[7]=a[2];
if(legal()){
outt();
break;
}
if (a[2]=='9') {
a[1]+=1;
a[2]='0';
} else {
a[2]+=1;
}
}
}
H题 子串分值
【问题描述】
对于一个字符串 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]) 的和是多少。
【解题思路】
动态规划。dp[x]记录从第一位至第x位的所有子串分值和。num[x][y]记录从第x位到第y位的分值。
主要思想：
对于第x位字符c，
找到其最后出现在1～x-1的位置j。
如果k<=j,
num[k][x]=num[k][x-1]
否则
num[k][x]=num[k][x-1]+1;
dp[x]=dp[x-1]+num[1][x]+num[2][x]+…+num[x][x]
dp[n]为最后结果。
【代码实现】
#include <iostream>
using namespace std;
int dp[100005],num[100005][100005];
int main(){
int i,j,k,n;
char a[100005];
cin>>a;
for (i=0; ; i++) {
if (a[i]=='\0') {
break;
}
}
n=i;
for (; i>0; i--) {
a[i]=a[i-1];
}
for (i=1; i<=n; i++) {
dp[i]=1;
num[i][i]=1;
}
for (i=2; i<=n; i++) {
for (j=i-1; j>=1; j--) {
if (a[j]==a[i]) {
break;
}
}
for (k=1; k<i; k++) {
if (k<=j) {
num[k][i]=num[k][i-1];
} else {
num[k][i]=num[k][i-1]+1;
}
}
for (j=1,dp[i]=dp[i-1]; j<=i; j++) {
dp[i]+=num[j][i];
}
}
cout<<dp[n]<<endl;
}
I题 平面切分
【问题描述】
平面上有 N 条直线，其中第 i 条直线是 y = Ai · x + Bi。
请计算这些直线将平面分成了几个部分。
【解题思路】
没想出解题方法，感觉有动态规划的味道。目前想出的，对于每一条新增的直线，前序直线的交点是否在此线上，是否与某条线平行，分情况讨论。
挖坑，有待更新lalala
J题 字串排序
【问题描述】
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。
总结
第一次参赛。比赛的时候可能是电脑有点问题，E题电脑没有运行出结果，浪费了将近一个小时找错，导致H题赛场有思路但是没时间写了，回寝室半个小时就写出来H了。
转载：https://blog.csdn.net/liuzeli78/article/details/109150521