2021年蓝桥杯国赛游记
06 Jun 2021
不知道赛委会怎么搞的，居然让我这种蒟蒻混进了国赛。明明省赛都在打暴力啊？
国赛试题难度和省赛好像不相上下，所以我后面几题也都拿不满，全是暴力混分…
考前
前一天不巧，有课程《操作系统》期末考试，时间都浪费在背八股文上了。考完抓紧回去背方程复习了。
图论背模板，数论背公式。动规背方程，高精背代码。——《骗分导论》
敲完几个经典dp后，复习数据结构。这回又上演经典老番：复习的都没考，考的都没复习。但我又不敢不复习，万一用上了呢…
最后 23：30 才睡觉。睡眠已不足 8 小时，明早要痛苦了。
考试当天
6：25 痛苦面具.jpg
6：55 面基了校内几位 ACM 大佬，大家互相膜拜了一番，然后我被白嫖 2 个口罩。
指导老师提前打好的出租车，准时出发去上海理工大学考点。公款消费，芜湖！！司机知道我们是竞赛选手，有点好奇我们老师在哪，好奇他怎么去考场。实际上，老师他很懒，咕了忙于科学事业，没空来。（情商++）
路上有一点点小堵，但很快也到了。我们从西南校门进去，一路上感受到浓厚的学术氛围。他们有光电信息研究院、光电信息与计算机工程学院，甚至还有档案馆（我校好像没有）。我们考场在计算中心。这里冒犯一句，这计算中心怎么跟个老式居民楼似的，一进门就只有窄楼梯，然后每层楼梯口都朝两边开出两个小门…
考场环境比省赛好多了，不再是两大排电脑。和对面一排的人尴尬地面对面的座位了，和左右的人间隔也比较大。我就喜欢这样的，自在。提前打好了头文件、快读和素数筛。
9：00 开考。4 道填空，6 道编程（为啥又改比例了？）。下面几段都是试题。
A 带宽为 $200$ Mbps 的网络，理论下载速度为 __ MB/s。（留给读者思考）
B 如果素数的所有十进制数位都是素数，则称为纯素数。比如 $23,37$ 是纯素数，$19,29$ 则不是。问给定区间有多少纯素数。
我已经提前打完了，开心。
C 如果某一天日期的年月日的数位之和是完全平方数，则称为完全日期。比如 2021 年 6 月 5 日 $= 2+0+2+1+6+5=16$ 是完全日期。问给定范围内有多少个完全日期。
好家伙，国赛还考儒略日，过分了。气得我差点没想起来闰年判法。
D 给定二叉树 $T$ 的权值函数 $W(T)=f(W(L),W(R),C(L),C(R))$，其中 $C(T)$ 代表 $T$ 上的结点个数，现在 $T$ 有 $2021$ 个结点，随便组合，问最小权值是多少？
这里 $W(T)$ 是一个多项式。我没见过这种题，只能空着了。
下面是编程题。
E 把输入的字符串里的小写字母都转为大写，输出最终的字符串。
喜闻乐见的签到题。
F 数列 $A=1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2…$，查询给定区间 $[L,R]$ 之和 $\sum_{i=L}^{R}A_i$。有多组数据。
（写多了，不感兴趣可略过）我是想象成类似这样的表格进行操作的：
| 行 | 末尾下标 | 元素 | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | ||||||
| 2 | 3 | 1 | 2 | |||||
| 3 | 6 | 1 | 2 | 3 | ||||
| 4 | 10 | 1 | 2 | 3 | 4 | |||
| 5 | 15 | 1 | 2 | 3 | 4 | 5 | ||
| 6 | 21 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
举个例子，求区间 $[8,25]$的和，图示是这样的：
| 行 | 末尾下标 | 元素 | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | ||||||
| 2 | 3 | 1 | 2 | |||||
| 3 | 6 | 1 | 2 | 3 | ||||
| 4 | 10 | 1 | 2 | 3 | 4 | |||
| 5 | 15 | 1 | 2 | 3 | 4 | 5 | ||
| 6 | 21 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
$S=2 \sim 4~+~1 \sim 5~+~1 \sim 6~+~1 \sim 4$（注：有些 LaTeX 版本不支持这个格式，建议看下式）
$S=\sum_{i=2}^{4}i+\sum_{i=1}^{5}i+\sum_{i=1}^{6}i+\sum_{i=1}^{4}i$
从左端点所在格子行累加到该行末尾，把右端点所在格子累加到该行起始，这可根据等差数列公式求得。中间几行类似。注意到各行末尾下标分别是 $1,1+2,1+2+3,…$，这也是等差数列的和。通过二分容易找到 $A_8$ 由于 $6 < 8 \leq 10$ 而在第 $4$ 行，右端点同理。于是能在 $O(T \log C)$ 时间完成所有查询。$C$ 为最大行数。根据 $C(C+1)/2 \geq max(R)$ 解得 $C \approx 1.5 \times 10^6$
G 把 01 字符串进行若干次异或变换，求最终结果。
这个有点像格雷码，我不会，打了暴力解。
H 问 $1 \sim N$ 中有多少数字在二进制下有 $K$ 个 1。
对于 30% 的评测用例，$1 \leq N \leq 10^6,1 \leq K \leq 10$
看到这数据范围，I’m angry。我知道有个递推式是 $f[i]=f[i/2]+(i \& 1)$，能在 $O(n)$ 时间计算 $i$ 在二进制下 1 的个数，但这波 $O(n \times {\rm sizeof}(long~long)))$ 时间的暴力法和递推拿的分是一样的，很伤。之后回来找规律，莫名其妙召唤出了迷之数列 $1,3,6,10,15,21,…$。最后也只是猜测要不要分类讨论它的二进制数位 $b_{max}$ 和 $b_{max-1…0}$，因为最高位有 $N$ 的限制。
I 给定圆括号序列。有 2 种操作：反转区间 $[L,R]$ （左括号变成右括号，右变左）和查询以 $L$ 为起点的最长合法序列。
J 求使小于 $n$ 的 3 个数 $a,b,c$ 满足 $a \oplus b \oplus c=0$ 且以这 3 个数为边长能组成三角形的方案数。
I 和 J 都不会做，只写了暴力解。继续研究 J 发现有趣的一点，取 $n=1,2,3,…$ 得到答案记为 $J_1,J_2,J_3,…$，令 $P_i=J_i-J_{i-1}$。如果画出 $P_i$ 的图像，会发现这也是个“带增量的周期数列”，只是不像 $1,1+2,1+2+3$ 那么有规律。但这并没有什么卵用。此外，这出题人也是老 Homo 了，样例里居然出现了 $114514$ 这个数字，太臭了。
做完还剩一个多小时，被罚坐。检查时发现写错不少地方。要么数组开小了，要么for(int i=1;i<=n;++i)忘记看n的取值导致i爆了int。最重要的进展是，我查出来一开始的素数筛写错了。
出考场，有 HXD 室友接我去饭馆白嫖了一顿。下午陪他买新电脑，以及乱逛。晚上，吃了一顿大餐（AA），然后从地铁站坐黑车回学校。黑车司机想一次多拉几个人，于是我们等了他亿会儿。司机师傅有点本事，竟拉来两个美少女👀！！太好了，可以和美少女贴贴了！！但是由于室友扛着机箱，车内拥挤，她们就走了。最后司机拉来一男的，我谔谔…