Coding的痕迹

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

0%

蓝桥杯 2021 比赛回忆

前天的时候参加了今年的蓝桥杯比赛,报了 C++ B组。比完之后有些忙,到现在虽然过去两天了,还是想写写自己的感受。

去年由于疫情原因,大约 10 月才比,也或许因此,题目比往年简单了一些。今年是第二次参加,却没准备多少,断断续续地总共写了一个多月力扣每日一题。比赛完之后感觉十题对了九题,可是一对答案发现一些题目在条件利用、数据范围上做得不够好,并因此写错。我认为这是比赛和做题经验的缺乏导致。或许今年年中会参加一次 PAT 计算机能力考试,还需要努力一把。

说说题吧。

第一题叫 “空间”,计算 256MB 内存可以存储多少个 32 位整数,打开计算器或者 python 解释器就可以算出来。

第二题叫 “卡片”,题目大意是:给定 2021 组 0~9 的卡片共 20210 张,去拼一系列从 1 开始的自然数(1, 2,…),问可以拼成多少个数。我模拟了生成卡片(generate)、判断是否可用(check)、去除卡片(remove_card)这三个过程,并把卡片存在一个 vector 里。

实际上,这里可以利用桶的思想,在一个数组 a[10] 中给每个元素放置 2021 张卡片,效率更高,程序也更好编写。

第三题叫 “直线”,求点集 {(x,y)0x<20,0y<21}\{(x, y) | 0 \leq x < 20, 0 \leq y < 21\} 中的点可以组成多少条不重复的直线。我刚看的时候,还煞有其事地用 Excel 拖了个表格,然后找规律算了半天,大约花了半个小时就转做后面题目了。到后面做不动时再回来看,发现可以设直线方程为 y=mnx+b\displaystyle y = \frac m n x + b,然后遍历点对 P(x1,y1)P(x_1, y_1)Q(x2,y2)Q(x_2, y_2),求得所有直线的解析式。用 $\frac m n $ 而不是系数 aa 是我担心浮点数精度不够,无法区分不同直线。现在回想起来也不知道考场上为什么会有这样的担心,设为 aa 其实是足够的。

此时离考试结束只有不到半小时,将直线方程用一个结构体(struct)表示,又用 std::unordered_set 存储直线方程,后来发现 unordered_set 不能对我的结构体进行哈希运算,std::set 也需要我重载 operator < 。实际上,任意写一个 < 的重载就可以,但我当时没想到,觉得数据量不大,用 vector 然后循环手写了 exist 函数,拿来当集合用。

第四题,叫 “货物摆放”。蓝桥杯这回用了个很大的数字 2021041820210418,尝试将这个数分解为三个整数之积。先在 python 解释器里看了下,用一个 unsigned long long 可以表示。然后发现数据量太大,需要优化。由于发现 sqrt 支持 long double 类型但是好像没有 long long 类型的版本,为了防止无法表示,先用 python 算了出结果。代码大概长这样子:

1
2
3
4
5
6
7
8
unsigned int  count = 0;
unsigned int s = /* 该数的平方根 */;
unsigned long long n = 2021041820210418;

for (int i = 1; i <= s; ++i)
for (int j = 1; j <= s; ++j)
if (n % (i * j) == 0)
count++;

但是我不知怎的当时突发奇想, s 用了 n 的立方根…跑出来的结果应该不对。

第五题是 “路径”,题目假设:aabb 两个节点之间权重为:若 a+b21a + b \leq 21,则为 aabb 最小公倍数。否则 aabb 不连通。一个图中共有 1~2021 共 2021 个节点,求节点 1 到 2021 的最短路径。用 Floyd 算法解的,但不知道结果对不对。

第六题是“时间显示”,将一个 1970 年 1 月 1 日 00:00 以来的毫秒数转换成时、分、秒的格式,比较常规。

第七题 “砝码称重”,给定 NN 个砝码,求能称重多重的物品。样例中已给提示,砝码可以放在填平的左盘或右盘,也就是意味着,我们可以将题目转换成:对于每个砝码(每一项),系数可能为 01-1,用类似三进制数的方法,逐个对每一位进行进位…得到算式,再求解出结果。每一个砝码用一个结构表示:

1
2
3
4
struct Weight {
int v; // 值
int c; // 系数
};

第八题是 “杨辉三角形”。给出一个数,求其第一次在杨辉三角形中出现时是第几个数。好久没写过倒是不大清楚怎么算了,只记得后一行的第 i 个值是前一行 i-1 项和第 i 项相加。考试的时候我把数据拷到 Excel 里,看上去更清楚一些。这题花了不少时间,实属不应该。我的思路是,维护一个 vector<int> 作为 cache 存储上一行的数据,然后每次更新它。用一个变量维护已遍历行的总数,用一个函数 search 返回数在一行中的索引。

后来和同学讨论时才发现,数据类型至少应该用 unsigned long,题目中所给的数据范围较大。同时,复用 “cache” 以减少内存的分配和销毁,可以减少运行时间。

第九题叫做 “双向排序”,较常规。开始我的 CodeBlocks 始终无法对 std::sort 函数进行提示,还在头文件 algorithm 中翻了会儿函数原型,后来凭自己的印象,想起来了 sort 的使用方法。平日里迭代器用得不少,但是关键时候对于区间开闭等问题还是踩了坑。

第十题是 “括号序列”,求让一个可能不匹配的括号序列恢复匹配有多少种方法。好像在力扣上看到过,但是没做,也就作罢。


回想这次比赛,我感觉到日常做题对参加算法竞赛有明显的帮助,但是做题仍然不够,一些算法没有仔细研究过,而 C++ STL 也在啃老本…

不过欣喜的是,自己解决问题的想法在发生变化,写的程序常常就一次性通过,写程序时的专注度也有所提高hhh

附上一张比赛结束后的图:

比赛现场图

以上。