原以为蓝桥杯省赛最高也就省二，没想到进了省一。不过因为是 B 组，不然真以为组委会把我名字放前边儿去了… 因为没有很多时间去写算法题，自己的水平也不高，在被通知进国赛时，犹豫了一段时间。后来问了问初、高中同学，还有家里人的意见，交了报名费决定去看一看、见识一下吧，心里还是很希望拿奖回本的 :D
算法的学习急不来。考前找了一下往年的试题，感觉不是我的水平能应付的——想了想也是，考虑到进国赛同学的水平，组委会也就没有必要出简单题了，便没怎么复习，挑选着看了看 bilibili 上蓝桥杯的复习课，想着在考场上碰碰运气、啃啃老本。
赛题
先说说题。
第一题“带宽”，计算 200Mbps 相当于 1 秒钟传输多少 MB 的数据。我当时内心：我是不是拿错题了，拿了省赛的题，好像之前国赛的题没有这样啊……
第二题“纯质数”。定义一个数如果是质数，且各个位是质数（2，3，5，7），那么它是一个纯质数。求 1 ~ 20210605 之间纯质数的个数。在编译选项里加了 -O3 让程序跑得快一点hhh
第三题“完全日期”。如果一个日期的年、月、日各个位加起来等于一个平方数，那么称为完全日期。题目要求计算 2001-01-01 到 2021-12-31 之间的完全日期的个数。稍微优化了一下，做了个平方表，然后写了个函数 jump_next_day 去迭代遍历，倒也简单。
第四题“最小权值”。题目大意是：给定二叉树 T 的权值函数 W(T)=f(W(L), W(R),C(L),C(R))，其中 C(T) 代表 T 上的结点个数，现在 T 有 2021 个结点，随便组合，求最小权值。大概扫了一眼觉得自己不会，先跳过。
后面开始是编程大题。第五题是“大写”，将一个长度为 1 ~ 100 的、仅包含大小写字母的字符串转换成大写并输出。我为什么对题目细节记得这么清楚呢？因为一直担心这题目有陷阱，仔仔细细读了几遍。
第六题“123”。给定一个数列 \{x_n\} = 1, 1, 2, 1, 2, 3, \dots，求第 l 项到第 r 项的和，但是题目所给的范围是，对于一半左右的数据在 10^6 以内，对于全部的测试用例，在 10^{18} 以内。用 Python （也可以口算，10^3 \approx 2^{10} ）算了下，差不多可以用 unsigned long long 去处理。
因为一开始思路不清晰，走的方向错了，这道题从九点半到十一点半做了将近两个小时，浪费了很多时间。一开始思考：我们把中间的一小节叫作一个段（section），段内的标号叫作偏移（offset）。所以数列就变成，一个长度为 1 的段，后面接着长度为 2 的段，…… 我们想根据项数，求得段号和段内偏移，编写函数 void query_pos(ull Sn, ull §ion, ull &offset);
利用等差数列求和公式 \displaystyle S_n = \frac {n(n+1)} {2} 想了2个方案：
- 解出 \displaystyle n = \frac {\sqrt {8 S_n + 1} - 1} {2}，向下取整就可以得到所在行号了，不过在计算过程中可能出现溢出。
- 将 S_n 乘 2 然后开根号可以得到一个比 n 小一点的数。由于将 S_n 乘 2 的操作可能导致溢出（没细研究），也可以先开根号，再乘以 \sqrt 2 \approx 1.414。其实，这和上一个解法的方案一样。得到初步的 n 后循环往上尝试，得到 n 的值。
在代码编写过程中，隐藏了很多 bug，使得这样一个简单的函数，却耗费了我大量时间。而且赛场上 Code::Blocks 和 DevC++ 的代码补全有些抽风，不太适合我这种函数命名长的选手……
重在参与，重在参与！计算得到段号和段内偏移之后，将中间段求和相加，然后补上首尾两段的差值即可。因为每一段的最大长度就等于段号，所以比较好算的是。不过我最后忘了这茬，没有用求和公式，而是用拿循环累加，可能在大数据量的时候丢好多分… 所以啊，比赛前一定要写代码！不然手生，容易犯错、考虑不周。
第七题“异或变换”。假定一个串长度为 n 的二进制序列 \{s_1, s_2, s_3, \dots, s_n\}，对其进行如下操作记为一次变换：s_1' = s_1，s_n' = s_{n-1} \oplus s_n (n \geq 2)。求对于给定的长度为 n 的二进制序列，经过 t 次变换后的二进制序列为多少。
这题最终暴力做了，但是对于全部测试用例 1 \leq t \leq 10^{30}，一定是有其他做法的。
第八题“二进制问题”，寻找 1 ~ N 中二进制 1 的个数为 K 的数的个数。比如，K = 2，在 1 ~ 8 中有 011，101，110 三个数作为结果。尽管最终交了暴力解法的代码，但是做了一些尝试：
-
当 N = 100 时，对不同 K 值下：
对着这张表看了半天，也就发现了一个规律：K = 1 时有 1、2、4、8、16、32、64，而 K = 2 里存在 3、5、9、17、33、65。但是细想发现， 也不好从 K = 1 推出 K = 2 时的数字，便作罢。
-
考虑一个二进制数
1 0010，可以把它分成两部分：0 0000~0 1111和1 0000~1 0010。对于前一个范围，二进制位有 K 个 1 的数字个数为 C_4^K （K \leq 4），后一个范围中二进制位有 K 个 1 的数字个数为 C_2^{K-1} （K \leq 1），将两个范围的数字加起来就好了。可惜后来没有时间写完，也不知道自己的考虑是否全面。
后面两题分别是“翻转括号序列” 和 “异或三角”，大概看了一眼不是很记得。
总结
再来附一张比赛后的照片：
就当做一次放松吧。比赛之后，在考点上海理工大学里转了转，红砖、绿树，十分美丽。树荫是成片的，内心很羡慕。
又和同学去外滩转了一转。一年多没去，那儿依旧繁华。远处，浦东那一栋栋高楼，见证者改革开放以来上海的发展。近处，不知道什么鸟儿，绕着游船，映着夕阳、在江上盘旋着、歌唱。
