【B类比赛】 第十一届蓝桥杯 省国赛经历_蓝桥杯是a类竞赛还是b类

Now

拿起键盘写下这段话的时候，已经是第12届蓝桥杯省赛前的一天了（2021.4.17）。
距离上次蓝桥杯省赛正好6个月了。
如今的我仍在ACM里，这半年经历了挺多事情，退ACM已经势在必行，且行且珍惜吧。
未来的我将会接触一些新的领域，在算法之路上大概不会再冲锋在前了。

---

蓝桥杯说明

考试方面：
1.5道填空+5道大题， 4个小时，9点到13点，qust是在弘毅D402到405考试.
2.填空题的答案怎么算出来都可以，可以写程序，可以用计算器，也可以用excel表格出答案（如果题目真的用得到的话）。
3.填空只需要提交最后答案，大题需要提交完整程序，每道题在比赛结束前无限次提交，每道题以最后一次提交为准。
4.比赛过程中没有分数反馈信息，也就是说，只有出成绩的时候你才知道自己做的怎么样，而且还不告诉你分数。
5.拿到省一才有资格打国赛。
难度方面：
大部分题目不需要算法，只需要代码基本功，要有逻辑思维能力，最主要是还是细心，代码基本功要扎实！
获奖方面：
奖项设置是10%为省一等奖，20%省二等奖，30%省三等奖，总共有60%同学可以获奖。但我校获奖率将近90%，获奖还是很简单的。山东b组省一需要做对至少5道题（做不出五道来，每道题尽可能多拿部分分也是可以的），具体情况在下面可以见到。

---

最初

在2019年刚入学的时候就听说过这个比赛了，
但是当时蓝桥杯并不是国家B类竞赛，
认可度不高，当时想报名但是没有成功。

---

省赛

在2020年，学校修订了《竞赛》类的比赛，蓝桥杯变成了国家B级竞赛。
初次参赛是疫情返校后的大二上学期，举办的是第十一届蓝桥杯，
大一一年并没有怎么好好学习，也没有参加过比赛，
从某种意义上来讲，这是我本科参加的第一场国家B级竞赛。
当时的自己只知道这个比赛很重要，但并没有意识到一个国家B级竞赛以后评奖评优和保研会那么重要。

第11届蓝桥杯第二场省赛试题
省一分数线大概是：3个填空+2个完整大题（出成绩后估的）

A题 门牌制作
数区间内数字2的个数，不难。
NOIP2010 数字统计 （算是原题吧）

B题 既约分数
gcd为1的点对数，不难，辗转相除法，代码也很短。

C题 蛇形填数
矩阵斜着填数而已，for循环模拟即可，不难。
NOIP2014 螺旋矩阵（类似题目）

D题 跑步锻炼
先算出总天数来，记录为s1
再算出包含了多少个周一，记录为s2
再算出包含了多少个月，记录为s3
再算出有多少个月的一号也是周一，记录为s4。
答案是s1+s2+s3-s4(不是很复杂的容斥，应该有更好的方法，我做这题花了很多时间)

E题 七段码
不难，给边编号，临界矩阵建边。
dfs枚举每条边选或不选两种情况，再用bfs判联通。
没学过dfs bfs的同学可能会被卡住。

F题 成绩统计
模拟题，不难，注意是浮点型运算。

G题 回文日期
NOIP2016 回文日期 原题？
题目很熟悉，不枚举每一个日期，而是枚举年，构造月和日，判断是否合法。
但题目没有说AAAAAAAA型的日期是否归到题目说的分类中（此处应该是出题人问题，别人也没考虑到，我考虑到了。所以对于1111年11月11日的日期，不计数，也不知道对不对。）

H题 子串分值和
有点难度了，感觉像是DP题，
答案是long long存的（用long long读了数据）。
读完题，只会 $N^{2}lo{g}_{2}N$ 的暴力做法，这才只有50%的分数。
想到了一个奇怪做法，考虑每个字符串最大价值为26，如果枚举每个首字母，再枚举区间长度，那么显然区间长度越长，这段字符串价值贡献的答案一定不减，那么就满足二分性，关键就在于找字符串价值变化的位置，那用vector记录每个字母出现的下标，然后枚举起点+二分找答案变化点，$N\ast 26\ast lo{g}_{2}N$， 可以过！。

I题 平面切割
第一反应不会做，但是N取值范围较小时可以模拟算出来答案，写很多if拿部分分。
前面的题感觉都会做，也都能做对，就没有仔细思考这道题，
为后续没进山东省前二十买下了伏笔。

J题 字串排序
花了快一个小时打完了n<=20的表，还手玩了一些样例，发现没问题。
先写上20行if(n == 1/2/3/4…)吧，然后观看构造，有规律但是没看出具体是什么规律……
返回去检查，确定一定能拿到8个大题+2个大题部分分，省一应该是稳了。

赛后：
I题 每新增一条直线，答案会+(k+1),k为这条直线与其他线的交点数（比赛的时候完全没往这方面想），很可惜，本来是可以将近ak的！

---

省赛成绩 和到国赛的那几周经历

在知乎查到了填空题答案，5个题全对，大题也许没写挂。
省赛成绩，山东省rk30+名，省一。
ACM的W队友，省20+名，M队友省前十。tql。

进国赛了，
国赛是 省一等奖的前5% 为国一，而我的省赛排名大概是5%到6%，这样算刚刚被卡出国一。
国赛必须取得比省赛好的成绩才能拿到国一……

以监考需要手机为由 换掉了华为nova2s，买了红米K30S至尊版。

省赛30多名，是我高中noip参赛时想都不敢想的成绩，不过大概率是沾了报名b组的光。

---

国赛

难度确实比省赛大了一点，但题目好歹对胃口。
不至于像第12届蓝桥杯省赛（下一篇博文）一样让我没有体验。

A.美丽的2
跟省赛第一题一样，不难。

B.扩散
4个起点的bfs，不难。

C.阶乘约数
高中数学题，但要有质数分解的思想。
答案是 (质因子次幂+1)的乘积，开 long long。

D.本质上升序列
一眼不会，下一题

E.玩具蛇
跟B题一样，转dfs，不难。

F.皮亚诺曲线
分治题？数据范围也大，特殊情况也多……
思考了很久，毕竟是第一个大题，半小时还没有啥好思路，感觉要完。
不会，下一题！

G.游园安排
按字典序从小到大排列，完全可以将名字抽象成数字。
然后要字典序递增且为首的字符串尽可能字典序小，那不就是导弹拦截裸题？
1e6个字母，那就是dp+二分。
NOIP1999导弹拦截
顺利过了。

H.答疑
无厘头的题目，明显为了出题而出题。
读完感觉像贪心，但是数据范围只有1000（应该可以扩展成10^5）。
然后进办公室时间和问答时间为什么不合并成一个变量？
为什么离开的时间一定是10、20、30秒，这是不是什么性质？
实在想不出有什么逻辑，应该上述全是干扰信息。
感觉 $O(n\ast lo{g}_{2}N)$的排序好像就可以了
用几年前张浩威讲过的简单贪心证明：
设第一个人 进办公室+回答问题的时间为 $A_1$，离开消耗 $B_1$
第二个人同理，则设先第一个人再第二个人的 时间消耗顺序 优于 先第二个人再第一个人。
那么可得不等式
$A_1$ + $(A_1+B_1+A_2)$ $<$ $A_2$ + $(A_2+B_2+A_1)$
移向得 $A_1+B_1<A_2+B_2$ ，也就是说将 $A_i+B_i$ 从小到大排序然后计算就好了。
很奇怪的 $n=1000$ 的 $O(N\ast lo{g}_{2}N)$ 题。

I.出租车
题太长了，先看下一题。

J.质数行者
很奇怪的dp题，数据范围不是很友好，还有一些点不可到达。
预处理小质数，
枚举长宽高，枚举质数转移，拿部分分就是了。

I题出租车不可做，F题曲线也不可做，D题也不可做。
J题剩余部分分也想不出来怎么做。
检查了每道题，测了很多数据，成绩也就那样了。
预计得分80到90的样子，满分是150，比起省赛来低太多了……

---

赛后

对了对答案，写上的4个填空还有2个大题都全对，最后一题部分分。三个题空着。

天梯赛前，出蓝桥杯成绩了。
C++ B组全国三十多名，排名大概在省一的前 $1\%$。
分数大概是 5 + 5 + 10 + 15 + 20 + 20 + 10 = 85分左右？
没想到空了三道题也能拿国一……应该是该拿到的分都拿到了吧。

M同学也是国一，全国前十，实在是tql。
我校两个国一，在山东省B组都是省前十，打的漂亮。

上了大学的第一场大型比赛，国一收场，良好开端…

---