第十一届蓝桥杯省赛C/C++ B组试题解析
第十一届蓝桥杯省赛C/C++ B组试题解析
第十一届蓝桥杯省赛C/C++ B组试题解析，包含所有试题的解题思路、代码实现以及一些解题技巧。对于参加蓝桥杯比赛的选手来说具有很高的参考价值。
试题A 签到题
可爱的签到题了，直接枚举，统计2出现的次数
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int cnt = 0;
for(int i = 1; i <= 2020;i++)
{
int x = i;
while(x)
{
if(x % 10 == 2) cnt++;
x /= 10;
}
}
cout << cnt;
return 0;
}
试题B 既约分数
填空题答案：2481215
题目描述
蓝桥云课链接
解题报告
看到求最大公约数，那么欧几里得算法(gcd)应该会在脑海中浮现出来吧~
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
//gcd
int gcd(int a,int b)
{
return b ? gcd(b,a%b):a;
}
int main()
{
int cnt = 0;
for(int i = 1; i <= 2020;i++)
for(int j = 1; j <= 2020;j++)
{
if(gcd(i,j) == 1) cnt++;
}
cout << cnt;
return 0;
}
试题C 蛇形填数
填空题答案：761
题目描述
蓝桥云课链接
解题报告
可以很明显的感觉到，这是属于找规律的题了。考试的时候担心自己手画出来的图不标准或者看着别扭，可以直接使用windows自带的画图进行模拟，规律就会十分明显了。
可以很清楚的看到： 1行1列是1
2行2列是5
3行3列是13
4行4列是25
那么：
第i个数和第（i-1）之间相差(i-1)*4
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int ans = 1;
for(int i = 2;i <= 20; ++i) ans += 4 * (i - 1);
cout<<ans;
return 0;
}
试题D 跑步锻炼
填空题答案：8879
题目描述
蓝桥云课链接
解题报告
读题不慎，自以为小蓝只是在周一和月初跑步。
我刚才去看了一下泡泡在b站上发的讲解视频，觉得他采用推理的方式解出来也是不错的。我将链接放在这里了哈，需要的小伙伴自行选择呀~
蓝桥杯2020省赛B组填空题解析/第十一届蓝桥杯真题
因为蓝桥杯中对时间处理一直是一块热门，这个题刚好设计了日期处理、平年闰年判断以及星期处理，就拿它作为讲解了。
一、平年闰年的判断
情况①：可以直接整除400
情况②：可以整除4的时候，不能再整除100了，比如1900年这个例子。
int leap = year % 100 && year % 4 == 0 || year % 400 ==0;
二、月份的处理
因为月份有30天，有31天的，甚至还有28、29的，想系统的枚举是不太方便的，可以考虑打表，然后查询指定月份的天数。
int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
三、本题解题思路
首先：咱们可以 用0 ~ 6表示周一到周天。
其次：用cnt统计2000年1月1日到某年某月某日所经过的天数
因为2000年1月1日是周六，按照咱们上面的规定，
此时能够通过( cnt(此时为0) + 5 )%7也就能够对应上咱们规定的数组中，周六应该有的下标。
其他的星期数，比如2000年1月3号的时候，cnt为2嘛，就可以精准的定位出，这天是周一，其他的每一天，也可以使用类似的方式来确定出是星期几。对于本题而言，只要取模之后是0的日期，就是星期一。
最后了：因为2020年10月1日是孤零零的一天，就单独处理它吧。
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int year)
{
return year % 400 == 0 || year % 4 == 0 && year % 100;
}
int get_day(int year,int month)
{
//判断平年闰年
if(is_leap(year) && month == 2) return days[month] + 1;
return days[month];
}
int main()
{
//从2000年枚举到2019年吧，然后单独处理2020年的九个月+1天
int cnt = 0;//统计到2000年1月1日的天数
int ans = 0;
for(int i = 2000; i <= 2019;i++)
for(int j = 1; j <= 12;j++)
{
//枚举这些日子里，月初的时候
for(int k = 1;k <= get_day(i,j);k++)
{
//算周几
int w = (cnt + 5) % 7;
//如果是月初或者是周一
if(k == 1 || w == 0) ans += 2;
else ans ++;
cnt ++;
}
}
//单独处理2020年的1~9月
for(int i =1;i <= 9;i++)
{
for(int k = 1;k <= get_day(2020,i);k++)
{
//算周几
int w = (cnt + 5) % 7;
//如果是月初或者是周一
if(k == 1 || w == 0) ans += 2;
else ans ++;
cnt ++;
}
}
//记得加上10月1号
ans += 2;
cout << ans;
return 0;
}
实际考试的时候，更加建议去数吧，这种写代码，里面的细节还挺多的，可能得不偿失。看到有用excel解的，我不太懂该怎么操作。
试题E 七段码
填空题答案：80
题目描述
蓝桥云课链接
解题报告
看到连通块，向着并查集的方向思考。但是我自己没有A出来，看了大佬的题解，发现自己太呆了，妄想只是借用一个并查集……
大佬的题解
解题核心：DFS + 并查集
先用dfs枚举出二极管的所有亮灭情况；再用并查集判断是否只有一个连通块；
用1 ~ 7来代表a ~ g；若某两个二极管相邻，那么就在它们之间连一条边
；
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int ans;//统计结果
int p[N];//存放并查集中，根信息的数组
bool st[N];//记录DFS搜索的状态
int e[N][N];//记录七段码灯管彼此连通的的信息,e[i[[j]表示i和j的连通与否
//补全并查集的核心函数
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
//补全DFS函数
void dfs(int u)
{
//设置递归结束的边界！
if(u == 8)
{
//并查集的初始化
for (int i = 1; i <= 7; i ++) p[i] = i;
//枚举这些被操作过灯管，检查连通情况
for(int i = 1; i <= 7; i++)
for(int j = 1; j <= 7;j++)
{
//i是点亮了。j是点亮了。i和j之间是直接联系的
if(st[i] && st[j] && e[i][j])
{
//放到一个连通块中
p[find(i)] = find(j);
}
}
int cnt = 0;
for(int i = 1; i <= 7;i++)
//当前灯管是亮的，而且形成一个连通块的了
if(st[i] && p[i] == i) cnt++;
if(cnt == 1) ans ++;
return ;
}
//递归环节
st[u] = 1;//打开当前灯管的情况
dfs(u+1);
st[u] = 0;
dfs(u+1);//关闭当前灯管的情况
}
int main()
{
//初始化1到7号，各个灯管，直接连通的情况
e[1][2] = e[1][6] = 1;//意思就是，代表a号灯管的的1，和代表b的2号灯管连通，和代表f的6号灯管连通
e[2][1] = e[2][3] = e[2][7] = 1;
e[3][2] = e[3][7] = e[3][4] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][7] = e[5][6] = 1;
e[6][1] = e[6][7] = e[6][5] = 1;
e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
//从1号灯管开始DFS
dfs(1);
cout << ans << endl;
return 0;
}
然后泡泡的视频里做数的方式咱们也是可以学学的，因为考试的时候，只要能Ac，比啥都好~
试题F 成绩统计
题目描述
蓝桥云课链接
解题报告
签到题了。
参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i <n;i++) cin >>a[i];
double ans1 = 0, ans2 = 0;
for(int i = 0; i < n;i++)
{
if(a[i] >= 60) ans1 += 1;
if(a[i] >= 85) ans2 += 1;
}
ans1 =(ans1/n)*100;
ans2 = (ans2/n)*100;
printf(“%.0f%%\n%.0f%%”,ans1,ans2);
return 0;
}
试题G 回文日期
题目描述
蓝桥云课链接
解题报告
对日期问题的考察，算是蓝桥杯中的一大热门了吧，就像喜欢考察和2相关的题一样。
这个题的考点是对日期的是否合法的判断，处理的时候，小伙伴们的思路不要乱。
先将日期中的年月日取出来，先判断月份。
再月份合法的情况下，处理不是2月情况下的天数是否合法；是2月的情况下，天数是否合法。这种下来，会清晰很多。
参考代码(C++版本)
//可恶，这个破题的数据范围是1000——100000
#include
#include
#include
using namespace std;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
//判断回文
bool check_vaild(int date)
{
//求出年份
int year = date / 10000;
//求出月份
int month = date % 10000 / 100;
//求出日子
int day = date % 100;
//判断月份是否合法
if(month == 0 || month > 12) return false;
if(day == 0 || month != 2 && day > days[month]) return false;
//处理二月，处理闰年和平年的事儿
if(month == 2)
{
int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
if(day > 28 + leap) return false;//就是在平年大于28，闰年大于29的时候，返回false
}
return true;
}
//判断回文+ ABABBABA,直接把上面代码搞下来，多加一个判断
bool check_vaild1(int date)
{
//求出年份
int year = date / 10000;
//求出月份
int month = date % 10000 / 100;
//求出日子
int day = date % 100;
//判断月份是否合法
if(month == 0 || month > 12) return false;
if(day == 0 || month != 2 && day > days[month]) return false;
//处理二月，处理闰年和平年的事儿
if(month == 2)
{
int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
if(day > 28 + leap) return false;//就是在平年大于28，闰年大于29的时候，返回false
}
if(day != month) return false;
return true;
}
int main()
{
int date1;
//题目输入一个年份
cin >> date1;
bool flag1 = false,flag2 =false;
for(int i = 1000; i < 9600; i++)
{
int date = i,x = i;
//将data翻转接在当前拥有的date后面。要掌握
for(int j = 0; j < 4;j++) date = date * 10 + x % 10,x /= 10;
//判断当前这个日期是不是在输入的日期范围之间以及检查当前这日期是否合法
if(!flag1 && date1 < date && date <= 99999999 && check_vaild(date))
{
flag1 = true;
cout << date << endl;
}
if(!flag2 && date1 < date && date <= 99999999 && check_vaild1(date))
{
flag2 = true;
cout << date << endl;
}
if(flag1 && flag2) break;
}
return 0;
}
试题H 子串分值
题目描述
蓝桥云课链接
解题报告
这个题我没有Ac，然后看到这个大佬的博客，发现是数学题。蓝桥杯—子串分值（数学）
按照y总曾经说的，算法选择上，其实可以优先考虑暴力，假如可以直接暴力出来，也不用折腾了。
对于这个题，就可以用两个for循环去逐一枚举，时间复杂度就是标椎的O(N^2)，因为最大的数据范围是10^5，那么O(N^2)的时间复杂度会超时的。但是毕竟蓝桥杯是OI赛制的，还是可以骗一部分分的。
外层循环i为起始位置控制；
内层