深圳幻海软件技术有限公司 欢迎您！
更多

蓝桥杯C++组怒刷50道真题（填空题）

2023-03-30

int for 蓝桥杯
🌼深夜伤感网抑云-南辰Music/御小兮-单曲-网易云音乐🌼多年后再见你-乔洋/周林枫-单曲-网易云音乐 18~22年真题，50题才停更，课业繁忙，有空就更，2023/3/18/23:01写下目录👊填空题🌼一,[蓝桥杯2020初赛]门牌制作🌼二,[蓝桥杯2020初赛]既约分数🌼

🌼深夜伤感网抑云 - 南辰Music/御小兮 - 单曲 - 网易云音乐

🌼多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐 

18~22年真题，50题才停更，课业繁忙，有空就更，2023/3/18/23:01写下

目录

👊填空题

🌼一,[蓝桥杯2020初赛] 门牌制作

🌼二,[蓝桥杯2020初赛] 既约分数

🌼三,[蓝桥杯2020初赛] 蛇形填数

🌼四,[蓝桥杯2020初赛] 七段码

🌼五,[蓝桥杯2020初赛] 约数个数

🌼六,[蓝桥杯2021初赛] 卡片

🌼七，[蓝桥杯2021初赛] 直线

🌼八,[蓝桥杯2021初赛] 货物摆放

🌼九,[蓝桥杯2021初赛] 路径

🌳Floyd-Warshall 

🌳Dijkstra  AC

🌼十, [蓝桥杯2021初赛] 空间 

🌼十一,[蓝桥杯2022初赛] 裁纸刀

🌼十二,[蓝桥杯2022初赛] 灭鼠先锋

🌼十三, [蓝桥杯2022初赛] 九进制转十进制

🌼十四, [蓝桥杯2022初赛] 顺子日期

🌼十五，[蓝桥杯2022初赛] 排列字母

🌼十六，[蓝桥杯2019初赛]平方和 

🌼十七，[蓝桥杯2019初赛]数列求值

🌼十八，[蓝桥杯2019初赛]最大降雨量

🌼十九，1455: [蓝桥杯2019初赛]迷宫

🌳BFS一  AC

🌳BFS二  AC

🌼二十，1462: [蓝桥杯2019初赛]组队

🌳观察法

🌳DFS

🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉

👊填空题总结 

⚠注意！！！编程题和填空题分成两个博客，毕竟50题，少说5万字，边敲边发布会很卡

编程题链接：  （未完待续）

-------------------------------------------------------

-------------------------------------------------------

👂 空 清新民谣版 - 汪小敏 - 单曲 - 网易云音乐

骗分过样例,暴力出奇迹;暴搜挂着机,打表出省一 (过去式了,看22年A组就知道)

2018，2019，2020，2021，2022年蓝桥杯C++／C组省赛A，B，G组真题

题目链接，题目， 解析，代码 

要参加2023年C++组A组省赛了！希望可以省一，没有也不要紧，还有大二 

当然，如果题目不对胃口，有些ACM银牌的大佬也才省二．．．对头的话，打铁选手也给你来个国一国二

和我一起刷进蓝桥杯C++A组省一（小声） 

👊填空题

咱先从20年开始

🌼一,[蓝桥杯2020初赛] 门牌制作

P1508 - [蓝桥杯2020初赛] 门牌制作 - New Online Judge (ecustacm.cn)

考虑到蓝桥杯OI赛制(没有反馈),最好自己多试几组例子,比如我,将代码第6行 i <= 2020分别改成23, 1, 19, 32测试了下,如果和草稿本算的一样,就算过了

否则真到比赛时信心满满,感觉自己AC了七八道题,最后连个省二都没就笑了  

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int sum = 0, j;
  6.     for(int i = 1; i <= 2020; ++i) {
  7.         j = i;
  8.         while(j / 10) {
  9.             if(j % 10 == 2)
  10.                 sum += 1;
  11.             j /= 10;
  12.         }
  13.         if(j % 10 == 2) sum += 1;
  14.     }
  15.     cout<<sum;
  16.     return 0;
  17. }
624

🌼二,[蓝桥杯2020初赛] 既约分数

P1509 - [蓝桥杯2020初赛] 既约分数 - New Online Judge (ecustacm.cn)

 用辗转相除法求最大公约数

原理: 原来的除数(➗右边的)  /  余数

  1. 1997 ÷ 615 = 3 (余 152)
  2. 615 ÷ 152 = 4(余7)
  3. 152 ÷ 7 = 21(余5)
  4. 7 ÷ 5 = 1 (余2)
  5. 5 ÷ 2 = 2 (余1)
  6. 2 ÷ 1 = 2 (余0)
  7. 至此，最大公约数为1
  1. #include<iostream>
  2. using namespace std;
  3. int com(int x, int y)
  4. {
  5.     while(x % y) { //辗转相除法
  6.         int z = x % y;
  7.         x = y;
  8.         y = z;
  9.     }
  10.     return y;
  11. }
  12. int main()
  13. {
  14.     int sum = 0;
  15.     for(int i = 1; i <= 2020; ++i)
  16.         for(int j = 1; j <= 2020; ++j)
  17.             if(com(i, j) == 1) sum++;
  18.     cout<<sum;
  19.     return 0;
  20. }
2481215

🌼三,[蓝桥杯2020初赛] 蛇形填数

P1510 - [蓝桥杯2020初赛] 蛇形填数 - New Online Judge (ecustacm.cn)

容易发现,数字按照 右-->左下-->下-->右上 的规律递增 

加个判断边界的条件即可

先画到45,可知,找第n行n列, i, j 需要遍历到2 * n - 1 

  1. #include<iostream>
  2. using namespace std;
  3. int a[1000][1000];
  4. int main()
  5. {
  6.     a[1][1] = 1;
  7.     int m = 1;
  8.     for(int i = 1, j = 1; i <= 40 && j <= 40;) {
  9.             //右
  10.             a[i][++j] = ++m;
  11.             //左下
  12.             while(1) {
  13.                 a[++i][--j] = ++m;
  14.                 if(j == 1) break;
  15.             }
  16.             //下
  17.             a[++i][j] = ++m;
  18.             //右上
  19.             while(1) {
  20.                 a[--i][++j] = ++m;
  21.                 if(i == 1) break;
  22.             }
  23.         }
  24.     cout<<a[20][20];
  25.     return 0;
  26. }
761

🌼四,[蓝桥杯2020初赛] 七段码

P1511 - [蓝桥杯2020初赛] 七段码 - New Online Judge (ecustacm.cn)

第一次做,猜了63种,错了,7 + 10 + 14 + 14 + 10 + 7 + 1 = 63

错在哪里呢,错在3,4,5段发光

而且由于不发光部分不需要连通,所以 3段 != 4段, 2段 != 5段

这道题单靠猜,90%的人都做不对,很容易就漏掉几种或者想当然

当然代码我也不会😂 

来个别人的AC代码把

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(int argc, char *argv[])
  5. {
  6.   // 请在此输入您的代码
  7.   int sum = 0;
  8.      
  9.     //有一段二极管发光; a,b,c,d,e,f,g
  10.     int l1 = 7;
  11.     //有两段二极管发光; ab,af,bc,bg,cg,cd,de,eg,ef,fg
  12.     int l2 = 10;
  13.     //有三段二极管发光; abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,cdg,deg,def,efg
  14.     int l3 = 16;//
  15.     //有四段二极管发光; abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defa
  16.     int l4 = 20;
  17.     //有五段二极管发光即有两端不发光; ab,ac,ad,ae,af,ag,bc,bd,be,bg,cd,cf,cg,de,df,dg,ef,eg,fg
  18.     int l5 = 19;//
  19.     //有六段二极管发光即有一端不发光; a,b,c,d,e,f,g
  20.     int l6 = 7;//(找一段二极管不发光的：)
  21.     //第七种情况，全部发光
  22.     int l7 = 1;
  23.      
  24.     sum = l1 + l2 + l3 + l4 + l5 + l6 + l7;
  25.     printf("%d\n", sum);
  26.   return 0;
  27. }

🌼五,[蓝桥杯2020初赛] 约数个数

P1514 - [蓝桥杯2020初赛] 约数个数 - New Online Judge (ecustacm.cn)

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int sum = 0;
  6.     for(int i = 1; i <= 1200000; ++i)
  7.         if(1200000 % i == 0) sum++;
  8.     cout<<sum;
  9.     return 0;
  10. }
96

到21年 

🌼六,[蓝桥杯2021初赛] 卡片

P1550 - [蓝桥杯2021初赛] 卡片 - New Online Judge (ecustacm.cn)

初始化a[10]为2021，对应着0~9，int k = i;  a[k % 10]--即可 

但是有个问题，代码虽然输出了正确答案，但是提交时显示编译错误，原来是语言选了C 

  1. #include<iostream>
  2. using namespace std;
  3. int a[10];
  4. int main()
  5. {
  6.     for(int i = 0; i <= 9; ++i)
  7.         a[i] = 2021; //初始化
  8.     int flag = 0;
  9.     for(int i = 1;; ++i) { //从1开始遍历
  10.         int k = i;
  11.         while(k) {
  12.             a[k % 10]--;
  13.             k /= 10;
  14.         }
  15.         for(int j = 0; j <= 9; ++j)
  16.             if(a[j] < 0) {
  17.                 cout<<i - 1;
  18.                 flag = 1; //到头了
  19.                 break;
  20.             }
  21.         if(flag) break;
  22.     }
  23.     return 0;
  24. }
3181

🌼七，[蓝桥杯2021初赛] 直线

P1551 - [蓝桥杯2021初赛] 直线 - New Online Judge (ecustacm.cn)

注意,除了下标和计数的now,其他都声明为double

而且第一次看成斜率相同算同一条直线了...

如果只是判断多少种斜率,最简单的set即可

但这里斜率 + 截距才能确定一条直线

一开始...犯了个重名的小错误, 找了半小时 + 百度 才找出来...

  1. set<pair<double, double>>b; //斜率k, 截距b
  2.     for(int i = 0; i < 420; ++i)
  3.         for(int j = 0; j < 420; ++j) {
  4.             if(a[i].x != a[j].x && a[i].y != a[j].y) {
  5.                 double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
  6.                 double b = a[i].y - k * a[i].x;
  7.                 b.insert({k, b});
  8.             }
  9.         }

报错error: request for member 'insert' in 'b', which is of non-class type 'double'

意思是, set变量名b和循环里面的double b重复了

修改后,第一次提交, 错了....(原因会在后面分析)

错误代码

  1. #include<iostream>
  2. #include<set> //set<>b;
  3. using namespace std;
  4. struct place
  5. {
  6.     double x, y; //横纵坐标
  7. };
  8. int main()
  9. {
  10.     struct place a[430];
  11.     int now = 0;
  12.     //读入420个点
  13.     for(double i = 0; i <= 19; ++i)
  14.         for(double j = 0; j <= 20; ++j) {
  15.             a[now].x = i;
  16.             a[now++].y = j;
  17.         }
  18.     //判断不同的直线
  19.     set<pair<double, double>>line; //斜率k, 截距b
  20.     for(int i = 0; i < 420; ++i)
  21.         for(int j = 0; j < 420; ++j) {
  22.             if(a[i].x != a[j].x && a[i].y != a[j].y) {
  23.                 double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
  24.                 double b = a[i].y - k * a[i].x;
  25.                 line.insert({k, b});
  26.             }
  27.         }
  28.     cout<<line.size() + 20 + 21; //加上竖和横
  29.     return 0;
  30. }
48953

而正确答案是40257

错误原因是double精度丢失 

k那里没问题, 问题是b那里,解决方案是

b = y1 - (y2 - y1) / (x2 - x1) * x1 ----> b = (y1 * (x2 - x1) - (y2 - y1) * x1) / (x2 - x1)

猜测是先除再减,会丢失更多精度.... 

AC代码 

当然,我用结构体写的有点乱了,意思就是这么个意思, y = kx + b, k = (y2 - y1) / (x2 - x1) 

核心思路就是斜率和截距确定一条直线 + set排除重合元素 + pair 

  1. #include<iostream>
  2. #include<set> //set<>b;
  3. using namespace std;
  4. struct place
  5. {
  6.     double x, y; //横纵坐标
  7. };
  8. int main()
  9. {
  10.     struct place a[430];
  11.     int now = 0;
  12.     //读入420个点
  13.     for(double i = 0; i <= 19; ++i)
  14.         for(double j = 0; j <= 20; ++j) {
  15.             a[now].x = i;
  16.             a[now++].y = j;
  17.         }
  18.     //判断不同的直线
  19.     set<pair<double, double>>line; //斜率k, 截距b
  20.     for(int i = 0; i < 420; ++i)
  21.         for(int j = 0; j < 420; ++j) {
  22.             if(a[i].x != a[j].x && a[i].y != a[j].y) { //排除横竖直线
  23.                 double k = (a[i].y - a[j].y) / (a[i].x - a[j].x);
  24.                 double b = (a[i].y * (a[i].x - a[j].x) -
  25.                             (a[i].y - a[j].y) * a[i].x) / (a[i].x - a[j].x);
  26.                 line.insert({k, b});
  27.             }
  28.         }
  29.     cout<<line.size() + 20 + 21; //加上竖和横
  30.     return 0;
  31. }
40257

🌼八,[蓝桥杯2021初赛] 货物摆放

P1552 - [蓝桥杯2021初赛] 货物摆放 - New Online Judge (ecustacm.cn)

虽然填空题不看复杂度,但是这么大的数,直接O(n^3)暴力肯定不行

容易发现,虽然是三个数,还是能用找因子的方法,用一个数组保存因子即可 

因子用取余 == 0的方式判断 

第一次敲完, 输出0.....然后一看int a[10000]里,单个数不能超过int,所以改long long就好了

  1. #include<iostream>
  2. #include<cmath> //sqrt()
  3. using namespace std;
  4. long long a[10010];
  5. int main()
  6. {
  7.     long long n = 2021041820210418, sum = 0, now = 0;
  8.     for(long long i = 1; i < sqrt(n); ++i)
  9.         if(n % i == 0) { //找出因子
  10.             a[now++] = i;
  11.             if(i * i != n) //判断另一个因子
  12.                 a[now++] = n / i;
  13.         }
  14.     for(int i = 0; i < now; ++i)
  15.         for(int j = 0; j < now; ++j)
  16.             for(int k = 0; k < now; ++k)
  17.                 if(a[i] * a[j] * a[k] == n) sum++;
  18.     cout<<sum;
  19.     return 0;
  20. }
2430

🌼九,[蓝桥杯2021初赛] 路径

P1553 - [蓝桥杯2021初赛] 路径 - New Online Judge (ecustacm.cn)  

看到最短路, 正好前天刚学了Floyd-Warshall和Dijkstra , 盘它

不会的可以看看这个博客

(5条消息) 最短路之Floyd-Warshall（10张图解）_码龄11天的博客-CSDN博客

(2条消息) 最短路之Dijkstra（15张图解）_迪杰斯特拉算法求最短路径图解_码龄?天的博客-CSDN博客

1,floyd是求多源最短路的

而且Floyd和Dijkstra都适用于稠密图(本题显然是稠密图)

假设n个顶点, m条边

看到没,这个才是稠密图(m >= n^2)

而一般的10个顶点,20条边这种,都是稀疏图(m << n^2)

Floyd核心思路还是中转 

2,将"路"读入二维数组e;  

3,第三个我们借辗转相除法间接求出最小公倍数

第一次敲完,无论是顶点1到2021还是顶点1到100,输出都是1e8,肯定哪里错了 

然后我对每一部分进行验算 

1,求公倍数函数com()没问题 

2,Floyd那里有问题 

  1. //利用中转求最短路
  2. for(int k = 1; k <= 2021; ++k)  //通过所有点中转
  3.     if(e[1][k] + e[k][2021] < e[1][2021])

为什么这段代码会让每次都输出无穷值呢?

因为你误以为Floyd可以求单源最短路. 它必须先通过求出多源最短路,才能找到单源的答案

只能用n^3先算出所有点的最短路,才能求1到2021的最短路

🌳Floyd-Warshall 

(本地AC, OJ上时间超限)

  1. #include<iostream>
  2. #include<cmath> //abs()
  3. using namespace std;
  4. int e[2050][2050];
  5. int inf = 1e9; //infinity无穷
  6.  
  7. int com(int x, int y)
  8. {
  9.     int a = x, b = y;
  10.     while(y) {
  11.         int z = x % y;
  12.         x = y;
  13.         y = z; //最后的x为公因数
  14.     }
  15.     return a * b / x; //最小公倍数
  16. }
  17.  
  18. int main()
  19. {
  20.     //初始化
  21.     for(int i = 1; i <= 2021; ++i)
  22.         for(int j = 1; j <= 2021; ++j) {
  23.             if(i == j) e[i][j] = 0; //自己到自己距离为0
  24.             else e[i][j] = inf;
  25.         }
  26.     //读入边的长度
  27.     for(int i = 1; i <= 2021; ++i)
  28.         for(int j = 1; j <= 2021; ++j) {
  29.             if(abs(i - j) <= 21 && i != j) {
  30.                 e[i][j] = com(i, j);
  31.                 e[j][i] = e[i][j]; //无向边
  32.             }
  33.         }
  34.     //利用中转求最短路(Floyd核心)
  35.     for(int k = 1; k <= 2021; ++k) //通过所有点中转
  36.         for(int i = 1; i <= 2021; ++i)
  37.             for(int j = 1; j <= 2021; ++j)
  38.                 if(e[i][k] + e[k][j] < e[i][j])
  39.                     e[i][j] = e[i][k] + e[k][j];
  40.     cout<<e[1][2021];
  41.     return 0;
  42. }

等了10秒才出结果(不要提交这个,这个在本地算出答案,只提交答案即可)

10266837

 提交时,怕超时,所以直接printf()

AC代码 

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<10266837;
  6.     return 0;
  7. }

 尽管时间复杂度达O(n^3), 大约是(2*10^3)^3 = 8e9, 也不是很大,毕竟顶点个数才2021个

所以填空题,一般建议暴力解决 + printf() 

------------------------------------------------------------------ 

下面,我再用Dijkstra做下这题 

Dijkstra的科普博客(6条消息) 最短路之Dijkstra（15张图解）_码龄11天的博客-CSDN博客

Dijkstra原理是贪心,而Floyd是动态规划 

1,初始化数组

2,循环

(1)确定源点到最近点的最短路径

(2)从刚被确定的点"出边"

🌳Dijkstra  AC

  1. #include<iostream>
  2. #include<cmath> //abs()
  3. using namespace std;
  4. int e[2050][2050], dis[2050], book[2050];
  5. int inf = 1e9; //infinity无穷
  6.  
  7. int com(int x, int y)
  8. {
  9.     int a = x, b = y;
  10.     while(y) {
  11.         int z = x % y;
  12.         x = y;
  13.         y = z; //最后的x为公因数
  14.     }
  15.     return a * b / x; //最小公倍数
  16. }
  17. int main()
  18. {
  19.     //初始化
  20.     for(int i = 1; i <= 2021; ++i)
  21.         for(int j = 1; j <= 2021; ++j) {
  22.             if(i == j) e[i][j] = 0; //自己到自己距离为0
  23.             else e[i][j] = inf;
  24.         }
  25.     //读入边的长度
  26.     for(int i = 1; i <= 2021; ++i)
  27.         for(int j = 1; j <= 2021; ++j) {
  28.             if(abs(i - j) <= 21 && i != j) {
  29.                 e[i][j] = com(i, j);
  30.                 e[j][i] = e[i][j]; //无向边
  31.             }
  32.         }
  33.     //初始化book和dis数组
  34.     for(int i = 1; i <= 2021; ++i) {
  35.         book[i] = 0;
  36.         dis[i] = e[1][i];
  37.     }
  38.     //Dijkstra
  39.     for(int i = 1; i <= 2020; ++i) { //n - 1次确定最短路
  40.         int Min = inf;
  41.         int u;
  42.         //找确定值
  43.         for(int j = 2; j <= 2021; ++j) { //1为源点，从下一个开始
  44.             if(book[j] == 0 && dis[j] < Min) {
  45.                 Min = dis[j];
  46.                 u = j;
  47.             }
  48.         }
  49.         book[u] = 1; //源点1号到u号的距离确定为最短路程
  50.         //从刚确定的点出边
  51.         for(int k = 2; k <= 2021; ++k) {
  52.             //两点连通且可更新
  53.             if(e[u][k] < inf && dis[k] > dis[u] + e[u][k])
  54.                 dis[k] = dis[u] + e[u][k];
  55.         }
  56.     }
  57.     cout<<dis[2021];
  58.     return 0;
  59. }
10266837

时间复杂度O(n^2),2021个点的数据量,直接提交也能过了

🌼十, [蓝桥杯2021初赛] 空间 

P1555 - [蓝桥杯2021初赛] 空间 - New Online Judge (ecustacm.cn)

一个32位二进制整数 = 4B, 1KB = 1024B,  1MB = 1024KB

所以  256MB = 256 * 1024 * 1024 / 4   个32位二进制整数 

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<256 * 256 * 1024;
  6.     return 0;
  7. }

到22年了

🌼十一,[蓝桥杯2022初赛] 裁纸刀

P2021 - [蓝桥杯2022初赛] 裁纸刀 - New Online Judge (ecustacm.cn)

🌼十二,[蓝桥杯2022初赛] 灭鼠先锋

P2022 - [蓝桥杯2022初赛] 灭鼠先锋 - New Online Judge (ecustacm.cn)

22年A组前两道填空题,放个以前的博客👇

(8条消息) 2022蓝桥杯省赛C++A组初尝试_码龄11天的博客-CSDN博客

🌼十三, [蓝桥杯2022初赛] 九进制转十进制

P2031 - [蓝桥杯2022初赛] 九进制转十进制 - New Online Judge (ecustacm.cn)

先让我们回忆下,十六进制转10怎么转的?

首先作为字符串输入 ,如果由0~9组成的十六进制数, 只需

  1. if(s[i] >= '0' && s[i] <= '9') 
  2.     sum += s[i] - '0';
  3. ......
  4. sum *= 16;

接下来有样学样就行,关键别人还给了确定的数

 2022(9) = 2 * 9^0 + 2 * 9^1 + 0 * 9^2 + 2 * 9^3

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int sum = 2 * 1 + 2 * 9 + 0 + 2 * 9*9*9;
  6.     cout<<sum;
  7.     return 0;
  8. }

粗心就会败北,第一次提交还写错个1,,,,真到蓝桥杯,一定要细心细心再细心

在草稿纸列清楚条条框框和细节,想尽可能多的, 特殊的样例 

🌼十四, [蓝桥杯2022初赛] 顺子日期

P2032 - [蓝桥杯2022初赛] 顺子日期 - New Online Judge (ecustacm.cn)

一开始我以为是任意年份，，，写了一堆字符串验证

然后看到了2022

先梳理思路，2022肯定构不成顺子，如果最后一个2开始构成顺子，2，3，4，需要第34月

也不可能 

细心细心再细心，不要想当然，老老实实列出所有情况 

所以只能从月，日入手：

1，01月 + 20~29日（10种）

2，10月 + 12日（1种）

3，11月 + 23日（1种）

4，12月 + 30~31日 （2种）

10 + 1 + 1 + 2 = 14

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {   
  5.     cout<<14;
  6.     return 0;
  7. }

 细心的人，高考能拿多50分；而粗心，足以使一个国二变成省二

🌼十五，[蓝桥杯2022初赛] 排列字母

P2041 - [蓝桥杯2022初赛] 排列字母 - New Online Judge (ecustacm.cn)

标签：入门题，模拟 

 按字符数组输入字符串，strlen()求字符数组字符串长度，sort()排序

  1. #include<iostream>
  2. #include<algorithm> //sort()
  3. #include<cstring> //strlen()
  4. using namespace std;
  5. int main()
  6. {
  7.     char s[20200] = "WHERETHEREISAWILLTHEREISAWAY";
  8.     sort(s, s + strlen(s));
  9.     cout<<s;
  10.     return 0;
  11. }
AAAEEEEEEHHHIIILLRRRSSTTWWWY

当然，这种填空题，自己直接排序，敲上去printf()也可

🌼十六，[蓝桥杯2019初赛]平方和 

P1452 - [蓝桥杯2019初赛]平方和 - New Online Judge (ecustacm.cn)

  1. #include<iostream>
  2. typedef long long LL;
  3. using namespace std;
  4. bool check(LL  n)
  5. {
  6.     while(n) {
  7.         LL m = n % 10;
  8.         if(m == 0 || m == 1 || m == 2 || m == 9)
  9.             return true;
  10.         n /= 10;
  11.     }
  12.     return false;
  13. }
  14. int main()
  15. {
  16.     LL sum = 0;
  17.     for(LL i = 1; i <= 2019; ++i) {
  18.         if(check(i))
  19.             sum += i * i;
  20.     }
  21.     cout<<sum;
  22.     return 0;
  23. }
2658417853

当然，最后提交时，我是这样提交的

  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<2658417853;
  6.     return 0;
  7. }

🌼十七，[蓝桥杯2019初赛]数列求值

P1453 - [蓝桥杯2019初赛]数列求值 - New Online Judge (ecustacm.cn)

第一次，求出0115，做错了。。

错误代码 

  1. #include<iostream>
  2. typedef long long LL;
  3. using namespace std;
  4. LL a[20200000];
  5. int main()
  6. {
  7.     a[1] = 1; a[2] = 1; a[3] = 1;
  8.     for(int i = 4; i <= 20190324; ++i) {
  9.         a[i] = a[i - 1] + a[i - 2] + a[i - 3];
  10.     }
  11.     cout<<a[20190324];
  12.     return 0;
  13. }
5268603393216230115

难道是超限了？应该是，考虑到题目说只需要最后四项，因为边取余边加不影响取余结果

所以我们在每一步加上取余10000

所以以后遇到，累乘或累加求最后几位数字的，每算一步取余一次 

因为边加边取余，或者边乘边取余，结果不变

  1. #include<iostream>
  2. typedef long long LL;
  3. using namespace std;
  4. LL a[20200000];
  5. int main()
  6. {
  7.     a[1] = 1; a[2] = 1; a[3] = 1;
  8.     for(int i = 4; i <= 20190324; ++i) {
  9.         a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 10000; //注意这里
  10.     }
  11.     cout<<a[20190324];
  12.     return 0;
  13. }
4659

AC代码

  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<4659;
  6.     return 0;
  7. }

🌼十八，[蓝桥杯2019初赛]最大降雨量

P1454 - [蓝桥杯2019初赛]最大降雨量 - New Online Judge (ecustacm.cn)

这是一道考研细心的题

审题一定要认真啊。。。

🌳Wrong Answer

读题时就感觉最大值是多少有点怪怪的，但没有细想，我把最大“降雨量”求出来不就完了？

所以，读题时感觉怪怪的地方，一定要多读几遍

搞清楚题目问的是什么，具体过程是什么

要亲自模拟一遍

如上图，这种情况降雨量最大，先草稿本算一遍，再代码来一次，一样，信心慢慢提交

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int ans = 0;
  6.     for(int i = 22; i <= 46; i += 4)
  7.         ans += i;
  8.     cout<<ans;
  9.     return 0;
  10. }
238

Wa!

🌳Accepted

看清楚，你所求出的238是最大的能量和，而降雨量为7周能量中位数，所以是34

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<"34";
  6.     return 0;
  7. }

🌼十九，1455: [蓝桥杯2019初赛]迷宫

P1455 - [蓝桥杯2019初赛]迷宫 - New Online Judge (ecustacm.cn)

这里介绍两种获得文件数据的方法

文件数据 oj.ecustacm.cn/upload/file/20200122/20200122134020_61830.txt

分析

⚠ 最短路杜绝dfs，指数级复杂度

下面针对是否读文件的2种情况，用bfsAC（01方阵最短路一般用bfs）

→ (5条消息) 《啊哈算法第四章之bfs》（17张图解）_千帐灯无此声的博客-CSDN博客

当然，由于填空题不考察时间复杂度（最后printf就行）所以一开始我还考虑了dijstra和Floyd

但这是01最短路，边权为1的地图，考虑bfs的模拟过程，显然bfs最合适

而Dij和Floy，做边权不为1的更合适

考察

1，读取数据

  1. for(int i=0;i<n;i++)
  2.     cin>>maze[i];

考虑到字符串按换行区分，整块粘贴过去就行

2，BFS模板，这个都要会

3，如何得到路径，网上搜了下看不懂（或者说懒得看了）

用自认为简单易懂的方式写了个（解释在注释里）

1，不用读文件

🌳BFS一  AC

我习惯用用数组模拟队列，就不用stl的queue了

关于输出路径，有个坑，第一次我少输出了第一步的D，因为最后得到路径写成这样了

  1. while(que[tail].f) {
  2.         ans += que[tail].al; //字符的连接
  3.         tail = que[tail].f; //更新队尾为上一个点
  4.     }

至于为什么会少输出第一步呢，请看图

假设最短路径为(1, 1), (2, 1), (3, 1), (4, 1)，假设此时来到(3, 1)

于是字符串ans加上了（到达(3, 1) 需要走的）方向，然后tail = (2, 1)所代表的下标（父坐标）

此时的que[tail].f 就已经是第一个点的下标了，在代码中也就是0，所以会漏了第一步

修改

while(que[tail].f) --> while(tail)

原始代码

然而直接提交显示答案错误（超时是不可能超时的），因为本题没有输入，它的本意就是考察读取文件数据传入字符变量

  1. #include<iostream>
  2. using namespace std;
  3. int tx, ty, flag, vis[100][100];
  4. string maze[30], ans;
  5. struct node
  6. {   //只要求输出最短路的路线,不要求输出具体步数,不用s
  7.     int x, y, f; //横坐标, 纵坐标, 父坐标
  8.     char al; //方向字母
  9. };
  10. int main()
  11. {
  12.     for(int i = 0; i < 30; ++i)
  13.         cin>>maze[i];
  14.     struct node que[1510]; //30 * 50
  15.     //方向数组, 由于D<L<R<U, 需要按这个顺序
  16.     int next[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
  17.     char dir[4] = {'D','L','R','U'}; //方向字母
  18.     //初始化队列
  19.     int head = 0, tail = 0;
  20.     //队列插入迷宫入口坐标
  21.     que[tail].x = 0;
  22.     que[tail].y = 0;
  23.     que[tail].f = 0;
  24.     que[tail].al = '0';
  25.     tail++;
  26.     //队列不为空
  27.     while(head < tail) {
  28.         //枚举4个方向
  29.         for(int i = 0; i < 4; ++i) {
  30.             //新的坐标
  31.             tx = que[head].x + next[i][0];
  32.             ty = que[head].y + next[i][1];
  33.             //超出范围
  34.             if(tx < 0 || ty < 0 || tx >= 30 || ty >= 50)
  35.                 continue;
  36.             //未访问过且不为障碍
  37.             if(vis[tx][ty] == 0 && maze[tx][ty] == '0') {
  38.                 vis[tx][ty] = 1; //标记
  39.                 que[tail].x = tx;
  40.                 que[tail].y = ty;
  41.                 que[tail].f = head;
  42.                 que[tail].al = dir[i];
  43.                 tail++;
  44.                 //BFS不需要取消标记, 只入队1次
  45.             }
  46.             //到达终点
  47.             if(tx == 29 && ty == 49) {
  48.                 flag = 1;
  49.                 break;
  50.             }
  51.         }
  52.         if(flag) break;
  53.         head++; //后续点的扩展
  54.     }
  55.     //用ans字符串保存从尾到头输出的路径
  56.     tail--; //最后的tail是队尾下一个,所以-1
  57.     while(tail) {
  58.         ans += que[tail].al; //字符的连接
  59.         tail = que[tail].f; //更新队尾为上一个点
  60.     }
  61.     for(int i = ans.size() - 1; i >= 0; --i)
  62.         cout<<ans[i];
  63.     return 0;
  64. }

直接将输出的答案复制，cout就好，所以填空题尽量本地DevC++得到答案后，再专门cout吧

貌似填空题一般也没有输入，只有输出 

输入输出

  1. 11001000110101000010101100011010011010101011110111
  2. 00011011010101001001001010000001000101001110000000
  3. 10100000101000100110101010111110011000010000111010
  4. 00111000001010100001100010000001000101001100001001
  5. 11000110100001110010001001010101010101010001101000
  6. 00010000100100000101001010101110100010101010000101
  7. 11100100101001001000010000010101010100100100010100
  8. 00000010000000101011001111010001100000101010100011
  9. 10101010011100001000011000010110011110110100001000
  10. 10101010100001101010100101000010100000111011101001
  11. 10000000101100010000101100101101001011100000000100
  12. 10101001000000010100100001000100000100011110101001
  13. 00101001010101101001010100011010101101110000110101
  14. 11001010000100001100000010100101000001000111000010
  15. 00001000110000110101101000000100101001001000011101
  16. 10100101000101000000001110110010110101101010100001
  17. 00101000010000110101010000100010001001000100010101
  18. 10100001000110010001000010101001010101011111010010
  19. 00000100101000000110010100101001000001000000000010
  20. 11010000001001110111001001000011101001011011101000
  21. 00000110100010001000100000001000011101000000110011
  22. 10101000101000100010001111100010101001010000001000
  23. 10000010100101001010110000000100101010001011101000
  24. 00111100001000010000000110111000000001000000001011
  25. 10000001100111010111010001000110111010101101111000
  26. DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

AC  代码

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
  6.     return 0;
  7. }

2，读文件

🌳BFS二  AC

读入文件只需要增加这些操作

maze.txt要和代码文件在同一目录下

  1. #include<fstream>
  2. ...
  3. //读取文件数据
  4.     ifstream infile("maze.txt"); //打开maze.txt文件
  5.     //按行读入maze.txt文件的字符串, 保存到maze数组中
  6.     for(int i = 0; i < 30; ++i)
  7.         getline(infile, maze[i]);

👆

原始代码

  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. int tx, ty, flag, vis[100][100];
  5. string maze[30], ans;
  6. struct node
  7. {   //只要求输出最短路的路线,不要求输出具体步数,不用s
  8.     int x, y, f; //横坐标, 纵坐标, 父坐标
  9.     char al; //方向字母
  10. };
  11. int main()
  12. {
  13.     //读取文件数据
  14.     ifstream infile("maze.txt"); //打开maze.txt文件
  15.     //按行读入maze.txt文件的字符串, 保存到maze数组中
  16.     for(int i = 0; i < 30; ++i)
  17.         getline(infile, maze[i]);
  18.  
  19.     struct node que[1510]; //30 * 50
  20.     //方向数组, 由于D<L<R<U, 需要按这个顺序
  21.     int next[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
  22.     char dir[4] = {'D','L','R','U'}; //方向字母
  23.     //初始化队列
  24.     int head = 0, tail = 0;
  25.     //队列插入迷宫入口坐标
  26.     que[tail].x = 0;
  27.     que[tail].y = 0;
  28.     que[tail].f = 0;
  29.     que[tail].al = '0';
  30.     tail++;
  31.     //队列不为空
  32.     while(head < tail) {
  33.         //枚举4个方向
  34.         for(int i = 0; i < 4; ++i) {
  35.             //新的坐标
  36.             tx = que[head].x + next[i][0];
  37.             ty = que[head].y + next[i][1];
  38.             //超出范围
  39.             if(tx < 0 || ty < 0 || tx >= 30 || ty >= 50)
  40.                 continue;
  41.             //未访问过且不为障碍
  42.             if(vis[tx][ty] == 0 && maze[tx][ty] == '0') {
  43.                 vis[tx][ty] = 1; //标记
  44.                 que[tail].x = tx;
  45.                 que[tail].y = ty;
  46.                 que[tail].f = head;
  47.                 que[tail].al = dir[i];
  48.                 tail++;
  49.                 //BFS不需要取消标记, 只入队1次
  50.             }
  51.             //到达终点
  52.             if(tx == 29 && ty == 49) {
  53.                 flag = 1;
  54.                 break;
  55.             }
  56.         }
  57.         if(flag) break;
  58.         head++; //后续点的扩展
  59.     }
  60.     //用ans字符串保存从尾到头输出的路径
  61.     tail--; //最后的tail是队尾下一个,所以-1
  62.     while(tail) {
  63.         ans += que[tail].al; //字符的连接
  64.         tail = que[tail].f; //更新队尾为上一个点
  65.     }
  66.     for(int i = ans.size() - 1; i >= 0; --i)
  67.         cout<<ans[i];
  68.     return 0;
  69. }

当然，最后提交还是要这个，因为蓝桥杯OJ不包含maze.txt这个文件

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
  6.     return 0;
  7. }

🌼二十，1462: [蓝桥杯2019初赛]组队

👂 十个字 - 褚晨茜/你的九儿 - 单曲 - 网易云音乐

P1462 - [蓝桥杯2019初赛]组队 - New Online Judge (ecustacm.cn)

team.txt链接 oj.ecustacm.cn/upload/file/20200122/20200122152423_34129.txt

思路

有点类似全排列，给定5个盒子，每个盒子一个数字，求最大的和

用dfs好了

当然，5 * 20这么点数据，100个数，一个一个数也给它数出来了

如果是50 * 50的数据量可能就算了

🌳观察法

注意，一个人只能同时打一个位置

我把每一列最高分的2~3个标记出来，如果某个队员只在唯一一个位置最高分，就选这个队员

当然，观察可知，17号选3号位的99分  或者  1号位的98分   是等价的 

98 + 99 + 98 + 97 + 98 = 490

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<490;
  6.     return 0;
  7. }

🌳DFS

1，数据直接复制到代码里

这种办法还行，就是加 ',' 有些烦，注意还得删去第一列的编号

  1. #include<iostream>
  2. using namespace std;
  3. int book[30], ans; //book[]的大小要大于20
  4. int c[20][5] = {
  5. {97, 90, 0 ,0, 0},
  6. {92, 85, 96, 0, 0},
  7. {0, 0, 0, 0, 93},
  8. {0, 0, 0, 80, 86},
  9. {89, 83, 97, 0, 0},
  10. {82, 86, 0, 0, 0},
  11. {0, 0, 0, 87, 90},
  12. {0, 97, 96, 0, 0},
  13. {0, 0, 89, 0, 0},
  14. {95, 99, 0, 0, 0},
  15. {0, 0, 96, 97, 0},
  16. {0, 0, 0, 93, 98},
  17. {94, 91, 0, 0, 0},
  18. {0, 83, 87, 0, 0},
  19. {0, 0, 98, 97, 98},
  20. {0, 0, 0, 93, 86},
  21. {98, 83, 99, 98, 81},
  22. {93, 87, 92, 96, 98},
  23. {0, 0, 0, 89, 92},
  24. {0, 99, 96, 95, 81}
  25. };
  26. void dfs(int step, int now) //当前第几号位
  27. {
  28.     if(step == 6) { //完成5个位置后, 结束递归
  29.         ans = max(ans, now);
  30.         return; //递归回上一个位置
  31.     }
  32.     //遍历
  33.     for(int i = 0; i < 20; ++i) {
  34.         if(book[i] == 0) { //第i号队员没被选上
  35.             book[i] = 1; //标记
  36.             dfs(step + 1, now + c[i][step - 1]); //递归
  37.             book[i] = 0; //取消标记
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     dfs(1, 0); //从1号位开始
  44.     cout<<ans;
  45.     return 0;
  46. }

注意第36行step要-1，因为c[20][5]里，第几列的下标从0开始，第5列的下标是4，所以step == 5时

下标应该为4，所以-1，否则数组超限会输出491

2，读取同一目录下的文件

关于将20行6列的team.txt读取到c[20][6]这个二维数组中

的操作

  1. #include<fstream> //ifstream读取文件
  2. ...
  3. //ifstream打开文件,命名为infile
  4.     ifstream infile("team.txt"); //文件名作为参数,""括起来
  5.     //读取文件每一个数字
  6.     for(int i = 0; i < 20; ++i)
  7.         for(int j = 0; j < 6; ++j)
  8.             infile >> c[i][j]; //存储到二维数组c
  9.     infile.close(); //关闭文件

原始代码

  1. #include<iostream>
  2. #include<fstream> //ifstream读取文件
  3. using namespace std;
  4. int book[30], ans, c[20][6];
  5. void dfs(int step, int now) //当前第几号位
  6. {
  7.     if(step == 6) { //完成5个位置后, 结束递归
  8.         ans = max(ans, now);
  9.         return; //递归回上一个位置
  10.     }
  11.     //遍历
  12.     for(int i = 0; i < 20; ++i) {
  13.         if(book[i] == 0) { //第i号队员没被选上
  14.             book[i] = 1; //标记
  15.             dfs(step + 1, now + c[i][step]); //递归
  16.             book[i] = 0; //取消标记
  17.         }
  18.     }
  19. }
  20. int main()
  21. {
  22.     //ifstream打开文件,命名为infile
  23.     ifstream infile("team.txt"); //文件名作为参数,""括起来
  24.     //读取文件每一个数字
  25.     for(int i = 0; i < 20; ++i)
  26.         for(int j = 0; j < 6; ++j)
  27.             infile >> c[i][j]; //存储到二维数组c
  28.     infile.close(); //关闭文件
  29.  
  30.     dfs(1, 0); //从1号位开始
  31.     cout<<ans;
  32.     return 0;
  33. }

AC  代码

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     cout<<490;
  6.     return 0;
  7. }

🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉

👊填空题总结 

1，预测23年题型

做了那么多2018，2019，2020，2021，2022的填空题，2023蓝桥杯省赛的填空题是什么呢，让我们猜猜看？和2023有关的前缀和或者字符串或者模拟？  

2，审题细心是关键

如果你只会模板题和暴力，那你绝对无缘国奖（虽然目前我的目标是A组省二）

首先，模板题可能出现各种变式，需要仔细观察题目，去模拟一下过程，再考虑对模板进行增删改

其次，读题不细心，导致，明明会做的，拿不到分，它让你输出A就别输出B（虽然A，B你都求出来了）

3，按行读取文件字符串，保存到字符串数组中

我先声明了string maze[30]，然后将同一目录下maze.txt中的30行字符串读入maze[30]

  1. #include<fstream>
  2. string maze[30];
  3. ...
  4. //读取文件数据
  5.     ifstream infile("maze.txt"); //打开maze.txt文件
  6.     //按行读入maze.txt文件的字符串, 保存到maze数组中
  7.     for(int i = 0; i < 30; ++i)
  8.         getline(infile, maze[i]);

按单个数字读取

  1. #include<fstream> //ifstream读取文件
  2. int c[20][6];
  3. ...
  4. //ifstream打开文件,命名为infile
  5.     ifstream infile("team.txt"); //文件名作为参数,""括起来
  6.     //读取文件每一个数字
  7.     for(int i = 0; i < 20; ++i)
  8.         for(int j = 0; j < 6; ++j)
  9.             infile >> c[i][j]; //存储到二维数组c
  10.     infile.close(); //关闭文件
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42515 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪