2021年蓝桥杯省赛游记

19 Apr 2021

第一次参加大型赛事，好激动噢

考前1天

下午复习数据结构

晚饭时间替室友打工做志愿服务（浪费了宝贵的复习时间）

晚上继续复习，特地看了一眼 Dijkstra，没想到真考了个模板题

睡前看《骗分导论》和欧拉筛，看不懂欧拉筛遂睡大觉

考试当天

6：20 起早坐校车赶往 SHU 考点

8：10 车快到的时候检查行李，发现没带准考证，幸好有电子版，于是骑车飙到打印店。返回时因车技太逊而撞倒一排共享单车，逃逸，素质–

8：45 在考场就坐，我左右两边都是妹子诶（右边妹子说她是来当炮灰的

9：15 正式开考。5 道填空，5 道编程

T1 问 256MB 空间能装多少个 int，我一看傻眼了，忘复习计算机基础了（

T2 数位计数，T3 几何题：求给定区间的格点能形成多少条不同的直线。随手敲了暴力走了

T4 考因数分解…一开始以为把素数筛掉，复杂度就正确了，但是在考场太紧张导致写不对素数判法。留了个 $O(n^2)$ 程序，跑到考试结束也没跑出结果

T5 考裸的 Dijkstra。我其实不会图的链式存储，只能老实靠邻接矩阵来解

T6 是蓝桥杯必考的儒略日…今年这题也忒恶心了，告诉你从 1970 年起经过的毫秒数，问当前时间是几时几分几秒。考场上做复杂了，从1年1月1日一直累加日期，直到剩下的秒数不足1天，再去处理。考后第2天才想起来，直接对它模 86400 就能得到当天秒数了…还好此题 $O(n)$ 时间勉强能过（$10^{18}÷1000÷86400÷365=3×10^7$）

T7 砝码称重。我想不出正解，打了个 dfs 上去，骗到一点分数（

T8 杨辉三角。我早上在车上翻书翻到了二项式定理但是认为不会考…交了个暴力程序。右边妹子好像写得很慢，途中忍受不了就提前离场了

T9 双向排序：对数组若干个区间进行若干次升序/降序排序，问最后数组长啥样。我在紫书上看到过类似的题，可惜忘了写法了。用 sort 交了暴力解 $O(mn\log n)$ 上去。本来还想改成桶排的，又想了想 $O(mnk)$ 时间估计和原来差不多，拿同样的分数但是我提交晚了就亏了（

T10 给定非法括号序列，求使用最少步数让它合法化的方法数。不会做。输样例+一点骗分技巧，希望至少能过一个测试点

水掉大部分的分之后还剩一个多小时，跑去推 T7，到结束了也没什么进展。左边的人不敲代码，一直在演算什么东西，以为是大佬，结果考完一看，她才提交了几道填空题…

13：15 考完就没啥事了。估分大约是省二，运气好一点省一…下午回家打游戏睡大觉（