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了，