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://www.uj5u.com/houduan/183499.html
標籤：python
上一篇：Github驚現高星神作，兩份演算法寶典讓你橫掃大廠演算法面試題
下一篇：MySQL學習筆記（一）