Coding的痕迹

一位互联网奔跑者的网上日记

0%

蓝桥杯 2021 国赛比赛回忆

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

算法的学习急不来。考前找了一下往年的试题,感觉不是我的水平能应付的——想了想也是,考虑到进国赛同学的水平,组委会也就没有必要出简单题了,便没怎么复习,挑选着看了看 bilibili 上蓝桥杯的复习课,想着在考场上碰碰运气、啃啃老本。

赛题

先说说题。

第一题“带宽”,计算 200Mbps 相当于 1 秒钟传输多少 MB 的数据。我当时内心:我是不是拿错题了,拿了省赛的题,好像之前国赛的题没有这样啊……

第二题“纯质数”。定义一个数如果是质数,且各个位是质数(2,3,5,7),那么它是一个纯质数。求 1 ~ 20210605 之间纯质数的个数。在编译选项里加了 -O3 让程序跑得快一点hhh

第三题“完全日期”。如果一个日期的年、月、日各个位加起来等于一个平方数,那么称为完全日期。题目要求计算 2001-01-012021-12-31 之间的完全日期的个数。稍微优化了一下,做了个平方表,然后写了个函数 jump_next_day 去迭代遍历,倒也简单。

第四题“最小权值”。题目大意是:给定二叉树 TT 的权值函数 W(T)=f(W(L),W(R),C(L),C(R))W(T)=f(W(L), W(R),C(L),C(R)),其中 C(T)C(T) 代表 TT 上的结点个数,现在 TT2021 个结点,随便组合,求最小权值。大概扫了一眼觉得自己不会,先跳过。

后面开始是编程大题。第五题是“大写”,将一个长度为 1 ~ 100 的、仅包含大小写字母的字符串转换成大写并输出。我为什么对题目细节记得这么清楚呢?因为一直担心这题目有陷阱,仔仔细细读了几遍。

第六题“123”。给定一个数列 {xn}=1,1,2,1,2,3,\{x_n\} = 1, 1, 2, 1, 2, 3, \dots,求第 ll 项到第 rr 项的和,但是题目所给的范围是,对于一半左右的数据在 10610^6 以内,对于全部的测试用例,在 101810^{18} 以内。用 Python (也可以口算,$10^3 \approx 2^{10} $)算了下,差不多可以用 unsigned long long 去处理。

因为一开始思路不清晰,走的方向错了,这道题从九点半到十一点半做了将近两个小时,浪费了很多时间。一开始思考:我们把中间的一小节叫作一个段(section),段内的标号叫作偏移(offset)。所以数列就变成,一个长度为 1 的段,后面接着长度为 2 的段,…… 我们想根据项数,求得段号和段内偏移,编写函数 void query_pos(ull Sn, ull &section, ull &offset);

利用等差数列求和公式 Sn=n(n+1)2\displaystyle S_n = \frac {n(n+1)} {2} 想了2个方案:

  1. 解出 n=8Sn+112\displaystyle n = \frac {\sqrt {8 S_n + 1} - 1} {2},向下取整就可以得到所在行号了,不过在计算过程中可能出现溢出。
  2. SnS_n 乘 2 然后开根号可以得到一个比 nn 小一点的数。由于将 SnS_n 乘 2 的操作可能导致溢出(没细研究),也可以先开根号,再乘以 21.414\sqrt 2 \approx 1.414。其实,这和上一个解法的方案一样。得到初步的 nn 后循环往上尝试,得到 nn 的值。

在代码编写过程中,隐藏了很多 bug,使得这样一个简单的函数,却耗费了我大量时间。而且赛场上 Code::Blocks 和 DevC++ 的代码补全有些抽风,不太适合我这种函数命名长的选手……

重在参与,重在参与!计算得到段号和段内偏移之后,将中间段求和相加,然后补上首尾两段的差值即可。因为每一段的最大长度就等于段号,所以比较好算的是。不过我最后忘了这茬,没有用求和公式,而是用拿循环累加,可能在大数据量的时候丢好多分… 所以啊,比赛前一定要写代码!不然手生,容易犯错、考虑不周。

第七题“异或变换”。假定一个串长度为 nn 的二进制序列 {s1,s2,s3,,sn}\{s_1, s_2, s_3, \dots, s_n\},对其进行如下操作记为一次变换:s1=s1s_1' = s_1sn=sn1sn(n2)s_n' = s_{n-1} \oplus s_n (n \geq 2)。求对于给定的长度为 nn 的二进制序列,经过 tt 次变换后的二进制序列为多少。

这题最终暴力做了,但是对于全部测试用例 1t10301 \leq t \leq 10^{30},一定是有其他做法的。

第八题“二进制问题”,寻找 1 ~ N 中二进制 1 的个数为 KK 的数的个数。比如,K=2K = 2,在 1 ~ 8 中有 011101110 三个数作为结果。尽管最终交了暴力解法的代码,但是做了一些尝试:

  1. N=100N = 100 时,对不同 KK 值下:

    对着这张表看了半天,也就发现了一个规律:K=1K = 1 时有 1、2、4、8、16、32、64,而 K=2K = 2 里存在 3、5、9、17、33、65。但是细想发现, 也不好从 K=1K = 1 推出 K=2K = 2 时的数字,便作罢。

  2. 考虑一个二进制数 1 0010,可以把它分成两部分:0 0000 ~ 0 11111 0000 ~ 1 0010。对于前一个范围,二进制位有 KK 个 1 的数字个数为 C4KC_4^KK4K \leq 4),后一个范围中二进制位有 KK 个 1 的数字个数为 C2K1C_2^{K-1}K1K \leq 1),将两个范围的数字加起来就好了。可惜后来没有时间写完,也不知道自己的考虑是否全面。

后面两题分别是“翻转括号序列” 和 “异或三角”,大概看了一眼不是很记得。

总结

再来附一张比赛后的照片:

赛后拍的考点照片

就当做一次放松吧。比赛之后,在考点上海理工大学里转了转,红砖、绿树,十分美丽。树荫是成片的,内心很羡慕。

上海理工大学 风景 1

上海理工大学 风景 2

又和同学去外滩转了一转。一年多没去,那儿依旧繁华。远处,浦东那一栋栋高楼,见证者改革开放以来上海的发展。近处,不知道什么鸟儿,绕着游船,映着夕阳、在江上盘旋着、歌唱。

上海 外滩风景 浦东