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

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

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

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 的立方根…跑出来的结果应该不对。

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

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

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

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

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

以上。