蓝桥杯C++组怒刷50道真题（填空题）
时间：2024-03-24 21:17:59 来源：网络cs 作者：付梓 栏目：平台政策 阅读：
🌼深夜伤感网抑云 - 南辰Music/御小兮 - 单曲 - 网易云音乐
🌼多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐
填空题25题完结，等23年题目出来了会补充，下一步就是编程题了
24年蓝桥杯之前，一定会给大家精心准备几个博客
目录
🎂第 15 届知识点大纲
🎂前言
👊填空题
🌼一,[蓝桥杯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
🌼二十一，1359: [蓝桥杯2018初赛]分数
🌼二十二，1360: [蓝桥杯2018初赛]星期一
🌼二十三，1361: [蓝桥杯2018初赛]乘积尾零
🌼二十四，1362: [蓝桥杯2018初赛]第几个幸运数
🌼二十五，1368: [蓝桥杯2018初赛]第几天
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
👊填空题总结
🎂第 15 届知识点大纲
后面几届，也可以参考，大同小异👇
考点内容，向上兼容，即 A 组 需要同时掌握 A，B，C组的内容
大学 C 组
大学 B 组
大学 A 组
🎂前言
⚠注意！！！编程题和填空题分成两个博客，毕竟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了七八道题,最后连个省二都没就笑了
#include<iostream>using namespace std;int main(){ int sum = 0, j; for(int i = 1; i <= 2020; ++i) { j = i; while(j / 10) { if(j % 10 == 2) sum += 1; j /= 10; } if(j % 10 == 2) sum += 1; } cout<<sum; return 0;}624🌼二,[蓝桥杯2020初赛] 既约分数
P1509 - [蓝桥杯2020初赛] 既约分数 - New Online Judge (ecustacm.cn)
用辗转相除法求最大公约数
原理: 原来的除数(➗右边的) / 余数
1997 ÷ 615 = 3 (余 152)615 ÷ 152 = 4(余7)152 ÷ 7 = 21(余5)7 ÷ 5 = 1 (余2)5 ÷ 2 = 2 (余1)2 ÷ 1 = 2 (余0)至此，最大公约数为1#include<iostream>using namespace std;int com(int x, int y){ while(x % y) { //辗转相除法 int z = x % y; x = y; y = z; } return y;}int main(){ int sum = 0; for(int i = 1; i <= 2020; ++i) for(int j = 1; j <= 2020; ++j) if(com(i, j) == 1) sum++; cout<<sum; return 0;}2481215🌼三,[蓝桥杯2020初赛] 蛇形填数
P1510 - [蓝桥杯2020初赛] 蛇形填数 - New Online Judge (ecustacm.cn)
容易发现,数字按照 右-->左下-->下-->右上 的规律递增
加个判断边界的条件即可
先画到45,可知,找第n行n列, i, j 需要遍历到2 * n - 1
#include<iostream>using namespace std;int a[1000][1000];int main(){ a[1][1] = 1; int m = 1; for(int i = 1, j = 1; i <= 40 && j <= 40;) { //右 a[i][++j] = ++m; //左下 while(1) { a[++i][--j] = ++m; if(j == 1) break; } //下 a[++i][j] = ++m; //右上 while(1) { a[--i][++j] = ++m; if(i == 1) break; } } cout<<a[20][20]; return 0;}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代码把
#include <stdio.h>#include <stdlib.h> int main(int argc, char *argv[]){ // 请在此输入您的代码 int sum = 0; //有一段二极管发光; a,b,c,d,e,f,g int l1 = 7; //有两段二极管发光; ab,af,bc,bg,cg,cd,de,eg,ef,fg int l2 = 10; //有三段二极管发光; abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,cdg,deg,def,efg int l3 = 16;// //有四段二极管发光; abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defa int l4 = 20; //有五段二极管发光即有两端不发光; ab,ac,ad,ae,af,ag,bc,bd,be,bg,cd,cf,cg,de,df,dg,ef,eg,fg int l5 = 19;// //有六段二极管发光即有一端不发光; a,b,c,d,e,f,g int l6 = 7;//(找一段二极管不发光的：) //第七种情况，全部发光 int l7 = 1; sum = l1 + l2 + l3 + l4 + l5 + l6 + l7; printf("%d\n", sum); return 0;}🌼五,[蓝桥杯2020初赛] 约数个数
P1514 - [蓝桥杯2020初赛] 约数个数 - New Online Judge (ecustacm.cn)
#include<iostream>using namespace std;int main(){ int sum = 0; for(int i = 1; i <= 1200000; ++i) if(1200000 % i == 0) sum++; cout<<sum; return 0;}96到21年
🌼六,[蓝桥杯2021初赛] 卡片
P1550 - [蓝桥杯2021初赛] 卡片 - New Online Judge (ecustacm.cn)
初始化a[10]为2021，对应着0~9，int k = i; a[k % 10]--即可
但是有个问题，代码虽然输出了正确答案，但是提交时显示编译错误，原来是语言选了C
#include<iostream>using namespace std;int a[10];int main(){ for(int i = 0; i <= 9; ++i) a[i] = 2021; //初始化 int flag = 0; for(int i = 1;; ++i) { //从1开始遍历 int k = i; while(k) { a[k % 10]--; k /= 10; } for(int j = 0; j <= 9; ++j) if(a[j] < 0) { cout<<i - 1; flag = 1; //到头了 break; } if(flag) break; } return 0;}3181🌼七，[蓝桥杯2021初赛] 直线
P1551 - [蓝桥杯2021初赛] 直线 - New Online Judge (ecustacm.cn)
注意,除了下标和计数的now,其他都声明为double
而且第一次看成斜率相同算同一条直线了...
如果只是判断多少种斜率,最简单的set即可
但这里斜率 + 截距才能确定一条直线
一开始...犯了个重名的小错误, 找了半小时 + 百度 才找出来...
set<pair<double, double>>b; //斜率k, 截距b for(int i = 0; i < 420; ++i) for(int j = 0; j < 420; ++j) { if(a[i].x != a[j].x && a[i].y != a[j].y) { double k = (a[i].y - a[j].y) / (a[i].x - a[j].x); double b = a[i].y - k * a[i].x; b.insert({k, b}); } }报错error: request for member 'insert' in 'b', which is of non-class type 'double'
意思是, set变量名b和循环里面的double b重复了
修改后,第一次提交, 错了....(原因会在后面分析)
错误代码
#include<iostream>#include<set> //set<>b;using namespace std;struct place{ double x, y; //横纵坐标};int main(){ struct place a[430]; int now = 0; //读入420个点 for(double i = 0; i <= 19; ++i) for(double j = 0; j <= 20; ++j) { a[now].x = i; a[now++].y = j; } //判断不同的直线 set<pair<double, double>>line; //斜率k, 截距b for(int i = 0; i < 420; ++i) for(int j = 0; j < 420; ++j) { if(a[i].x != a[j].x && a[i].y != a[j].y) { double k = (a[i].y - a[j].y) / (a[i].x - a[j].x); double b = a[i].y - k * a[i].x; line.insert({k, b}); } } cout<<line.size() + 20 + 21; //加上竖和横 return 0;}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
#include<iostream>#include<set> //set<>b;using namespace std;struct place{ double x, y; //横纵坐标};int main(){ struct place a[430]; int now = 0; //读入420个点 for(double i = 0; i <= 19; ++i) for(double j = 0; j <= 20; ++j) { a[now].x = i; a[now++].y = j; } //判断不同的直线 set<pair<double, double>>line; //斜率k, 截距b for(int i = 0; i < 420; ++i) for(int j = 0; j < 420; ++j) { if(a[i].x != a[j].x && a[i].y != a[j].y) { //排除横竖直线 double k = (a[i].y - a[j].y) / (a[i].x - a[j].x); double b = (a[i].y * (a[i].x - a[j].x) - (a[i].y - a[j].y) * a[i].x) / (a[i].x - a[j].x); line.insert({k, b}); } } cout<<line.size() + 20 + 21; //加上竖和横 return 0;}40257🌼八,[蓝桥杯2021初赛] 货物摆放
P1552 - [蓝桥杯2021初赛] 货物摆放 - New Online Judge (ecustacm.cn)
虽然填空题不看复杂度,但是这么大的数,直接O(n^3)暴力肯定不行
容易发现,虽然是三个数,还是能用找因子的方法,用一个数组保存因子即可
因子用取余 == 0的方式判断
第一次敲完, 输出0.....然后一看int a[10000]里,单个数不能超过int,所以改long long就好了
#include<iostream>#include<cmath> //sqrt()using namespace std;long long a[10010];int main(){ long long n = 2021041820210418, sum = 0, now = 0; for(long long i = 1; i < sqrt(n); ++i) if(n % i == 0) { //找出因子 a[now++] = i; if(i * i != n) //判断另一个因子 a[now++] = n / i; } for(int i = 0; i < now; ++i) for(int j = 0; j < now; ++j) for(int k = 0; k < now; ++k) if(a[i] * a[j] * a[k] == n) sum++; cout<<sum; return 0;}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那里有问题
//利用中转求最短路for(int k = 1; k <= 2021; ++k) //通过所有点中转 if(e[1][k] + e[k][2021] < e[1][2021])为什么这段代码会让每次都输出无穷值呢?
因为你误以为Floyd可以求单源最短路. 它必须先通过求出多源最短路,才能找到单源的答案
只能用n^3先算出所有点的最短路,才能求1到2021的最短路
🌳Floyd-Warshall
(本地AC, OJ上时间超限)
#include<iostream>#include<cmath> //abs()using namespace std;int e[2050][2050];int inf = 1e9; //infinity无穷int com(int x, int y){ int a = x, b = y; while(y) { int z = x % y; x = y; y = z; //最后的x为公因数 } return a * b / x; //最小公倍数}int main(){ //初始化 for(int i = 1; i <= 2021; ++i) for(int j = 1; j <= 2021; ++j) { if(i == j) e[i][j] = 0; //自己到自己距离为0 else e[i][j] = inf; } //读入边的长度 for(int i = 1; i <= 2021; ++i) for(int j = 1; j <= 2021; ++j) { if(abs(i - j) <= 21 && i != j) { e[i][j] = com(i, j); e[j][i] = e[i][j]; //无向边 } } //利用中转求最短路(Floyd核心) for(int k = 1; k <= 2021; ++k) //通过所有点中转 for(int i = 1; i <= 2021; ++i) for(int j = 1; j <= 2021; ++j) if(e[i][k] + e[k][j] < e[i][j]) e[i][j] = e[i][k] + e[k][j]; cout<<e[1][2021]; return 0;}等了10秒才出结果(不要提交这个,这个在本地算出答案,只提交答案即可)
10266837提交时,怕超时,所以直接printf()
AC代码
#include<iostream>using namespace std;int main(){ cout<<10266837; return 0;}尽管时间复杂度达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
#include<iostream>#include<cmath> //abs()using namespace std;int e[2050][2050], dis[2050], book[2050];int inf = 1e9; //infinity无穷int com(int x, int y){ int a = x, b = y; while(y) { int z = x % y; x = y; y = z; //最后的x为公因数 } return a * b / x; //最小公倍数}int main(){ //初始化 for(int i = 1; i <= 2021; ++i) for(int j = 1; j <= 2021; ++j) { if(i == j) e[i][j] = 0; //自己到自己距离为0 else e[i][j] = inf; } //读入边的长度 for(int i = 1; i <= 2021; ++i) for(int j = 1; j <= 2021; ++j) { if(abs(i - j) <= 21 && i != j) { e[i][j] = com(i, j); e[j][i] = e[i][j]; //无向边 } } //初始化book和dis数组 for(int i = 1; i <= 2021; ++i) { book[i] = 0; dis[i] = e[1][i]; } //Dijkstra for(int i = 1; i <= 2020; ++i) { //n - 1次确定最短路 int Min = inf; int u; //找确定值 for(int j = 2; j <= 2021; ++j) { //1为源点，从下一个开始 if(book[j] == 0 && dis[j] < Min) { Min = dis[j]; u = j; } } book[u] = 1; //源点1号到u号的距离确定为最短路程 //从刚确定的点出边 for(int k = 2; k <= 2021; ++k) { //两点连通且可更新 if(e[u][k] < inf && dis[k] > dis[u] + e[u][k]) dis[k] = dis[u] + e[u][k]; } } cout<<dis[2021]; return 0;}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位二进制整数
#include<iostream>using namespace std;int main(){ cout<<256 * 256 * 1024; return 0;}到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组成的十六进制数, 只需
if(s[i] >= '0' && s[i] <= '9') sum += s[i] - '0';......sum *= 16;接下来有样学样就行,关键别人还给了确定的数
2022(9) = 2 * 9^0 + 2 * 9^1 + 0 * 9^2 + 2 * 9^3
#include<iostream>using namespace std;int main(){ int sum = 2 * 1 + 2 * 9 + 0 + 2 * 9*9*9; cout<<sum; return 0;}粗心就会败北,第一次提交还写错个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
#include<iostream>using namespace std;int main(){ cout<<14; return 0;}细心的人，高考能拿多50分；而粗心，足以使一个国二变成省二
🌼十五，[蓝桥杯2022初赛] 排列字母
P2041 - [蓝桥杯2022初赛] 排列字母 - New Online Judge (ecustacm.cn)
标签：入门题，模拟
按字符数组输入字符串，strlen()求字符数组字符串长度，sort()排序
#include<iostream>#include<algorithm> //sort()#include<cstring> //strlen()using namespace std;int main(){ char s[20200] = "WHERETHEREISAWILLTHEREISAWAY"; sort(s, s + strlen(s)); cout<<s; return 0;}AAAEEEEEEHHHIIILLRRRSSTTWWWY当然，这种填空题，自己直接排序，敲上去printf()也可
🌼十六，[蓝桥杯2019初赛]平方和
P1452 - [蓝桥杯2019初赛]平方和 - New Online Judge (ecustacm.cn)
#include<iostream>typedef long long LL;using namespace std;bool check(LL n){ while(n) { LL m = n % 10; if(m == 0 || m == 1 || m == 2 || m == 9) return true; n /= 10; } return false;}int main(){ LL sum = 0; for(LL i = 1; i <= 2019; ++i) { if(check(i)) sum += i * i; } cout<<sum; return 0;}2658417853当然，最后提交时，我是这样提交的
#include <iostream>using namespace std;int main(){ cout<<2658417853; return 0;}🌼十七，[蓝桥杯2019初赛]数列求值
P1453 - [蓝桥杯2019初赛]数列求值 - New Online Judge (ecustacm.cn)
第一次，求出0115，做错了。。
错误代码
#include<iostream>typedef long long LL;using namespace std;LL a[20200000];int main(){ a[1] = 1; a[2] = 1; a[3] = 1; for(int i = 4; i <= 20190324; ++i) { a[i] = a[i - 1] + a[i - 2] + a[i - 3]; } cout<<a[20190324]; return 0;}5268603393216230115难道是超限了？应该是，考虑到题目说只需要最后四项，因为边取余边加不影响取余结果
所以我们在每一步加上取余10000
所以以后遇到，累乘或累加求最后几位数字的，每算一步取余一次
因为边加边取余，或者边乘边取余，结果不变
#include<iostream>typedef long long LL;using namespace std;LL a[20200000];int main(){ a[1] = 1; a[2] = 1; a[3] = 1; for(int i = 4; i <= 20190324; ++i) { a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 10000; //注意这里 } cout<<a[20190324]; return 0;}4659AC代码
#include <iostream>using namespace std;int main(){ cout<<4659; return 0;}🌼十八，[蓝桥杯2019初赛]最大降雨量
P1454 - [蓝桥杯2019初赛]最大降雨量 - New Online Judge (ecustacm.cn)
这是一道考研细心的题
审题一定要认真啊。。。
🌳Wrong Answer
读题时就感觉最大值是多少有点怪怪的，但没有细想，我把最大“降雨量”求出来不就完了？
所以，读题时感觉怪怪的地方，一定要多读几遍
搞清楚题目问的是什么，具体过程是什么
要亲自模拟一遍
如上图，这种情况降雨量最大，先草稿本算一遍，再代码来一次，一样，信心慢慢提交
#include<iostream>using namespace std;int main(){ int ans = 0; for(int i = 22; i <= 46; i += 4) ans += i; cout<<ans; return 0;}238Wa!
🌳Accepted
看清楚，你所求出的238是最大的能量和，而降雨量为7周能量中位数，所以是34
#include<iostream>using namespace std;int main(){ cout<<"34"; return 0;}🌼十九，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，读取数据
for(int i=0;i<n;i++) cin>>maze[i];考虑到字符串按换行区分，整块粘贴过去就行
2，BFS模板，这个都要会
3，如何得到路径，网上搜了下看不懂（或者说懒得看了）
用自认为简单易懂的方式写了个（解释在注释里）
1，不用读文件
🌳BFS一 AC
我习惯用用数组模拟队列，就不用stl的queue了
关于输出路径，有个坑，第一次我少输出了第一步的D，因为最后得到路径写成这样了
while(que[tail].f) { ans += que[tail].al; //字符的连接 tail = que[tail].f; //更新队尾为上一个点 }至于为什么会少输出第一步呢，请看图
假设最短路径为(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)原始代码
然而直接提交显示答案错误（超时是不可能超时的），因为本题没有输入，它的本意就是考察读取文件数据传入字符变量
#include<iostream>using namespace std;int tx, ty, flag, vis[100][100];string maze[30], ans;struct node{ //只要求输出最短路的路线,不要求输出具体步数,不用s int x, y, f; //横坐标, 纵坐标, 父坐标 char al; //方向字母};int main(){ for(int i = 0; i < 30; ++i) cin>>maze[i]; struct node que[1510]; //30 * 50 //方向数组, 由于D<L<R<U, 需要按这个顺序 int next[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; char dir[4] = {'D','L','R','U'}; //方向字母 //初始化队列 int head = 0, tail = 0; //队列插入迷宫入口坐标 que[tail].x = 0; que[tail].y = 0; que[tail].f = 0; que[tail].al = '0'; tail++; //队列不为空 while(head < tail) { //枚举4个方向 for(int i = 0; i < 4; ++i) { //新的坐标 tx = que[head].x + next[i][0]; ty = que[head].y + next[i][1]; //超出范围 if(tx < 0 || ty < 0 || tx >= 30 || ty >= 50) continue; //未访问过且不为障碍 if(vis[tx][ty] == 0 && maze[tx][ty] == '0') { vis[tx][ty] = 1; //标记 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; que[tail].al = dir[i]; tail++; //BFS不需要取消标记, 只入队1次 } //到达终点 if(tx == 29 && ty == 49) { flag = 1; break; } } if(flag) break; head++; //后续点的扩展 } //用ans字符串保存从尾到头输出的路径 tail--; //最后的tail是队尾下一个,所以-1 while(tail) { ans += que[tail].al; //字符的连接 tail = que[tail].f; //更新队尾为上一个点 } for(int i = ans.size() - 1; i >= 0; --i) cout<<ans[i]; return 0;}直接将输出的答案复制，cout就好，所以填空题尽量本地DevC++得到答案后，再专门cout吧
貌似填空题一般也没有输入，只有输出
输入输出
11001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRRAC 代码
#include<iostream>using namespace std;int main(){ cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR"; return 0;}2，读文件
🌳BFS二 AC
读入文件只需要增加这些操作
maze.txt要和代码文件在同一目录下
#include<fstream>...//读取文件数据 ifstream infile("maze.txt"); //打开maze.txt文件 //按行读入maze.txt文件的字符串, 保存到maze数组中 for(int i = 0; i < 30; ++i) getline(infile, maze[i]);👆
原始代码
#include<iostream>#include<fstream>using namespace std;int tx, ty, flag, vis[100][100];string maze[30], ans;struct node{ //只要求输出最短路的路线,不要求输出具体步数,不用s int x, y, f; //横坐标, 纵坐标, 父坐标 char al; //方向字母};int main(){ //读取文件数据 ifstream infile("maze.txt"); //打开maze.txt文件 //按行读入maze.txt文件的字符串, 保存到maze数组中 for(int i = 0; i < 30; ++i) getline(infile, maze[i]); struct node que[1510]; //30 * 50 //方向数组, 由于D<L<R<U, 需要按这个顺序 int next[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; char dir[4] = {'D','L','R','U'}; //方向字母 //初始化队列 int head = 0, tail = 0; //队列插入迷宫入口坐标 que[tail].x = 0; que[tail].y = 0; que[tail].f = 0; que[tail].al = '0'; tail++; //队列不为空 while(head < tail) { //枚举4个方向 for(int i = 0; i < 4; ++i) { //新的坐标 tx = que[head].x + next[i][0]; ty = que[head].y + next[i][1]; //超出范围 if(tx < 0 || ty < 0 || tx >= 30 || ty >= 50) continue; //未访问过且不为障碍 if(vis[tx][ty] == 0 && maze[tx][ty] == '0') { vis[tx][ty] = 1; //标记 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; que[tail].al = dir[i]; tail++; //BFS不需要取消标记, 只入队1次 } //到达终点 if(tx == 29 && ty == 49) { flag = 1; break; } } if(flag) break; head++; //后续点的扩展 } //用ans字符串保存从尾到头输出的路径 tail--; //最后的tail是队尾下一个,所以-1 while(tail) { ans += que[tail].al; //字符的连接 tail = que[tail].f; //更新队尾为上一个点 } for(int i = ans.size() - 1; i >= 0; --i) cout<<ans[i]; return 0;}当然，最后提交还是要这个，因为蓝桥杯OJ不包含maze.txt这个文件
#include<iostream>using namespace std;int main(){ cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR"; return 0;}🌼二十，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
#include<iostream>using namespace std;int main(){ cout<<490; return 0;}🌳DFS
1，数据直接复制到代码里
这种办法还行，就是加 ',' 有些烦，注意还得删去第一列的编号
#include<iostream>using namespace std;int book[30], ans; //book[]的大小要大于20int c[20][5] = {{97, 90, 0 ,0, 0},{92, 85, 96, 0, 0},{0, 0, 0, 0, 93},{0, 0, 0, 80, 86},{89, 83, 97, 0, 0},{82, 86, 0, 0, 0},{0, 0, 0, 87, 90},{0, 97, 96, 0, 0},{0, 0, 89, 0, 0},{95, 99, 0, 0, 0},{0, 0, 96, 97, 0},{0, 0, 0, 93, 98},{94, 91, 0, 0, 0},{0, 83, 87, 0, 0},{0, 0, 98, 97, 98},{0, 0, 0, 93, 86},{98, 83, 99, 98, 81},{93, 87, 92, 96, 98},{0, 0, 0, 89, 92},{0, 99, 96, 95, 81}};void dfs(int step, int now) //当前第几号位{ if(step == 6) { //完成5个位置后, 结束递归 ans = max(ans, now); return; //递归回上一个位置 } //遍历 for(int i = 0; i < 20; ++i) { if(book[i] == 0) { //第i号队员没被选上 book[i] = 1; //标记 dfs(step + 1, now + c[i][step - 1]); //递归 book[i] = 0; //取消标记 } }}int main(){ dfs(1, 0); //从1号位开始 cout<<ans; return 0;}注意第36行step要-1，因为c[20][5]里，第几列的下标从0开始，第5列的下标是4，所以step == 5时
下标应该为4，所以-1，否则数组超限会输出491
2，读取同一目录下的文件
关于将20行6列的team.txt读取到c[20][6]这个二维数组中
的操作
#include<fstream> //ifstream读取文件...//ifstream打开文件,命名为infile ifstream infile("team.txt"); //文件名作为参数,""括起来 //读取文件每一个数字 for(int i = 0; i < 20; ++i) for(int j = 0; j < 6; ++j) infile >> c[i][j]; //存储到二维数组c infile.close(); //关闭文件原始代码
#include<iostream>#include<fstream> //ifstream读取文件using namespace std;int book[30], ans, c[20][6];void dfs(int step, int now) //当前第几号位{ if(step == 6) { //完成5个位置后, 结束递归 ans = max(ans, now); return; //递归回上一个位置 } //遍历 for(int i = 0; i < 20; ++i) { if(book[i] == 0) { //第i号队员没被选上 book[i] = 1; //标记 dfs(step + 1, now + c[i][step]); //递归 book[i] = 0; //取消标记 } }}int main(){ //ifstream打开文件,命名为infile ifstream infile("team.txt"); //文件名作为参数,""括起来 //读取文件每一个数字 for(int i = 0; i < 20; ++i) for(int j = 0; j < 6; ++j) infile >> c[i][j]; //存储到二维数组c infile.close(); //关闭文件 dfs(1, 0); //从1号位开始 cout<<ans; return 0;}AC 代码
#include<iostream>using namespace std;int main(){ cout<<490; return 0;}🌼二十一，1359: [蓝桥杯2018初赛]分数
P1359 - [蓝桥杯2018初赛]分数 - New Online Judge (ecustacm.cn)
20项，意味着最后一项的分母是2^19，分子是2^0 + 2^1 + ... + 2^19，
得出分子分母后，辗转相除求最大公因数，输出分子分母除以最大公约数后的比值即可(互质)
本地编译器
#include<iostream>#include<cmath> //pow()using namespace std;//求最大公约数int com(int x, int y){ int temp; while(x % y) { temp = y; y = x % y; x = temp; } return y;}int main(){ int a = pow(2, 19); //a是分母 int b = 0; for(int i = 0; i < 20; ++i) b += pow(2, i); //b是分子 int max_com = com(a, b); cout<<b / max_com<<"/"<<a / max_com; return 0;}AC 代码
#include<iostream>using namespace std;int main(){ cout<<"1048575/524288"; return 0;}🌼二十二，1360: [蓝桥杯2018初赛]星期一
P1360 - [蓝桥杯2018初赛]星期一 - New Online Judge (ecustacm.cn)
本题有个坑（错了2次才做对。。），凡是算天数，最后都要 -1，比如1901/1/1到1901/2/3的天数，是31 + 3 - 1，
最后的 -1不要漏了，当然如果是1901/1/1 ~ 2001/1/1，这个不用减，但是到2000/12/31要
1，难点：1901/1/1到底星期几，这个得根据今天日期和星期得出
2，容易：求1901/1/1 ~ 2000/12/31之间的天数（闰年366天，其他365天）
我先写个代码，先得出1901/1/1和今天差了多少天，再得到1901/1/1是星期几
当然会datetime函数或者excel的可以直接得到1901是星期几，我懒得学了
//今天2023/4/5星期三#include<iostream>using namespace std;//int m[12] = {31,59,90,120,151,181,212,243,273,304,334,365};bool leap(int year){ if(year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)) return true; return false;}int main(){ int days = 0; for(int i = 1901; i <= 2022; ++i) {//先不算今年 if(leap(i)) days += 366; //闰年 else days += 365; //平年 } days = days + 31 + 28 + 31 + 5; //今年平年 //然而这里有个坑，得自己模拟下 //比如今天1月1,到2月5过了多少天呢,答案是31+5-1 //因为1月1到2月1是31天，而2月1到2月5是4天，没有5天 days -= 1; int ans = days % 7; cout<<ans; //输出2, 意味则着1901/1/1是星期一 return 0;}今天2023/4/5星期三，总天数是7的倍数多1，所以1901/1/1是星期二
1注意里面的坑，最后算出的days要-1，因为4月1到4月5只有4天，不能直接加上5
观察过程
//1901/1/1是星期二#include<iostream>using namespace std;bool leap(int year){ if(year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)) return true; return false;}int main(){ int days = 0; for(int i = 1901; i <= 2000; ++i) { if(leap(i)) days += 366; else days += 365; } //大坑，这里days要 -1 //如果是1901/1/1到2001/1/1就是2001 - 1901年,但现在只到2000/12/31 days -= 1; int ans1 = days / 7; //1901/1/1 ~ 2000/12/31总周数 int ans2 = days % 7; //多出来的几天 cout<<ans1<<" "<<ans2; return 0;}5217 5表示5217周多5天，因为今天是星期二，过多5天才星期天，所以是5217个星期一
AC 代码
#include<iostream>using namespace std;int main(){ cout<<5217; return 0;}🌼二十三，1361: [蓝桥杯2018初赛]乘积尾零
P1361 - [蓝桥杯2018初赛]乘积尾零 - New Online Judge (ecustacm.cn)
思路
1，
以前遇到过一题类似的（求阶乘末尾0的个数）
具体参考这篇第3题第1小题二分算法学习_千帐灯无此声的博客-CSDN博客
暴力得到乘积显然会超过long long的范围1e18
因为10 = 2 * 5，所以转化为统计每个数中2和5的因子数（写个函数）
比如625 = 5 * 5 * 5 * 5，16 = 2 * 2 * 2 * 2，625 * 16 = 10000，因为2和5因字数取min
是4，所以末尾4个0
2，
这里还涉及文件的读入（按单个数字读取），我将会基于注释简单易懂的写出来（具体看代码）
还有一种是字符串按行读入，具体参考本博客结尾第3个总结
product.txt要和C++代码在同一目录下，类似这样
本地 代码
看着很长，思路很清晰
#include<iostream>#include<fstream> //文件读入的头文件using namespace std;int a[20][20], num_2, num_5; //全局变量自动初始化为0void pro(int x){ while(1) { //先统计5的因子数 if(x % 5 == 0) { x /= 5; num_5 += 1; } else break; } while(1) { //再统计2的因子数 if(x % 2 == 0) { x /= 2; num_2 += 1; } else break; }}int main(){ ifstream infile("product.txt"); //打开文件 //读入文件中单个数据 for(int i = 0; i < 10; ++i) for(int j = 0; j < 10; ++j) infile>>a[i][j]; infile.close(); //关闭文件 //遍历得到答案 for(int i = 0; i < 10; ++i) for(int j = 0; j < 10; ++j) pro(a[i][j]); cout<<min(num_2, num_5); return 0;}等了2秒后才跳出答案，填空题千万别直接提交
31来看看本地代码和cout的区别（填空题暴力就OK，注意不要超限）
AC 代码
#include<iostream>using namespace std;int main(){ cout<<31; return 0;}🌼二十四，1362: [蓝桥杯2018初赛]第几个幸运数
P1362 - [蓝桥杯2018初赛]第几个幸运数 - New Online Judge (ecustacm.cn)
暴力也许。。跑5分钟都没有答案？或者你可以让它先跑着，你先去写下一题？🙃
数字接近6e13，所以开long long
既然它只包含3，5，7这三种因子，不妨假设59084709587505 = 3^i + 5^j + 7^k
直接对i, j, k展开遍历好了
额外的测试
令num = 49
10然而下面的本地代码，直接提交也AC了！，只能说pow的精度误差卡了49，没卡59084709587505
虽然pow(3, 0) * pow(5, 0) * pow(7, 2) == 49，但是代码中的if那里，并不会在49时自增ans
要到50才自增到11（BUG代码AC了）
据说pow的精度丢失在VC和VS不会发生，codeblocks才存在
本地 代码
#include<iostream>#include<cmath> //pow()using namespace std;long long ans, num = 59084709587505;int main(){ for(int i = 0; pow(3, i) <= num; ++i) for(int j = 0; pow(5, j) <= num; ++j) for(int k = 0; pow(7, k) <= num; ++k) if(pow(3, i) * pow(5, j) * pow(7, k) <= num) ans++; //初始有个1 == 3^0 * 5^0 * 7^0 == 1 cout<<ans - 1; //减去初始的1 return 0;}AC 代码
#include<iostream>using namespace std;int main(){ cout<<1905; return 0;}🌼二十五，1368: [蓝桥杯2018初赛]第几天
P1368 - [蓝桥杯2018初赛]第几天 - New Online Judge (ecustacm.cn)
写个短点的代码（这是B组的填空题，上面的是A组的，差别真大）
2000 % 400 == 0，闰年2月29天
看清题目，1月1是第1天，而不是第0天
所以1月31是第31天，2月1是第1 + 31天，3月1是第1 + 31 + 29天，4月1是第1 + 31 + 29 + 31天，
5月1是第1 + 31 + 29 + 31 + 30天，5月4就再加上1->2，2->3，3->4，共3天
所以答案是1 + 31 + 29 + 31 + 30 + 3
AC 代码
#include<iostream>using namespace std;int main(){ cout<<1 + 31 + 29 + 31 + 30 + 3; return 0;}做这种题，没什么好方法，一个一个数才能提高正确率
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
👊填空题总结
1，预测23年题型
做了那么多2018，2019，2020，2021，2022的填空题，2023蓝桥杯省赛的填空题是什么呢，让我们猜猜看？和2023有关的前缀和或者字符串或者模拟？
2，审题细心是关键
如果你只会模板题和暴力，那你绝对无缘国奖（虽然目前我的目标是A组省二）
首先，模板题可能出现各种变式，需要仔细观察题目，去模拟一下过程，再考虑对模板进行增删改
其次，读题不细心，导致，明明会做的，拿不到分，它让你输出A就别输出B（虽然A，B你都求出来了）
3，按行读取文件字符串，保存到字符串数组中
我先声明了string maze[30]，然后将同一目录下maze.txt中的30行字符串读入maze[30]
#include<fstream>string maze[30];...//读取文件数据 ifstream infile("maze.txt"); //打开maze.txt文件 //按行读入maze.txt文件的字符串, 保存到maze数组中 for(int i = 0; i < 30; ++i) getline(infile, maze[i]);按单个数字读取
#include<fstream> //ifstream读取文件int c[20][6];...//ifstream打开文件,命名为infile ifstream infile("team.txt"); //文件名作为参数,""括起来 //读取文件每一个数字 for(int i = 0; i < 20; ++i) for(int j = 0; j < 6; ++j) infile >> c[i][j]; //存储到二维数组c infile.close(); //关闭文件4，日期类题目
能一个一个数就一个一个数，比如2023/4/8是星期六，问你2023天后的年月日，以及星期几
4/8到5月8是多少天呢？
或者2023年1月1日是今年第1天，问你第100天是几月几号，这时你就数到2023/1/31是第31天，所以2/1是第 1 + 31天，而不是第31天
这类题往往差了1个数，就错了，谨慎的去数数，不要想当然
阅读本书更多章节>>>>本文链接：https://www.kjpai.cn/zhengce/2024-03-24/148152.html，文章来源：网络cs，作者：付梓，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！