蓝桥杯 2021 国赛比赛回忆

原以为蓝桥杯省赛最高也就省二，没想到进了省一。不过因为是 B 组，不然真以为组委会把我名字放前边儿去了… 因为没有很多时间去写算法题，自己的水平也不高，在被通知进国赛时，犹豫了一段时间。后来问了问初、高中同学，还有家里人的意见，交了报名费决定去看一看、见识一下吧，心里还是很希望拿奖回本的 😄

算法的学习急不来。考前找了一下往年的试题，感觉不是我的水平能应付的——想了想也是，考虑到进国赛同学的水平，组委会也就没有必要出简单题了，便没怎么复习，挑选着看了看 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 &section, 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$ ），将两个范围的数字加起来就好了。可惜后来没有时间写完，也不知道自己的考虑是否全面。