蓝桥杯2021省赛游记 | C/C++ | 大学A组

今天想起来还没有写这次比赛的游记，那就写一下吧。

第一次参加蓝桥杯 ，因为 ACM 搞不动 ，前几天出成绩了——黑龙江省一，还是稍微有点意外的，主要是因为今年蓝桥杯的省赛题简直一言难尽：说它水吧，感觉不比 NOIP 简单，更是比往年的赛题难不少；说它难吧，其实暴力打得好就会有省一。

赛前

其实本来不想参加这次比赛的，毕竟性价比比较低，因为身在哈工大，参加此类比赛，花费 300 大洋除了能在简历上加一行，在其他方面如保研等没有任何好处，不像其他大学参加蓝桥杯有各种加分。

不过后来还是决定参加了，因为大一下要专业分流，几乎没有时间卷 ACM，所以还是考一下蓝桥杯保持一下手感吧。

比赛日

这次比赛我选择哈尔滨学院赛点，考前遇到了形如考试机里没有 DevCpp 只有 CodeBlocks 等鬼畜问题，根据规定是可以向组委会投诉的，好在[数据删除]，最终我还是成功用上了 DevCpp 来比赛。

题面

直接在这里看吧，就不搬运了。

A 题

第一题还是普及组水平的签到题。

直接开一个 $0 \sim 9$ 的桶，每个桶存 $2021$ 张卡，从 $1$ 开始遍历自然数集，逐数字数位分离，每分离一个数，对应位置的桶减去 $1$ ，直到出现一个数 $n$ 的某一位减不动, $n-1$ 就是答案。

好像几分钟就秒了这题。

B 题

这题我第一反应是类似 NOIP 2017 D2T3 的仪仗队暴力版，不过其实操作会稍微复杂一点， $dp[x1][y1][x2][y2]$ 表示 $(x1, y1), \ (x2, y2)$ 已经有线连接，遍历所有没有线连接的点元组，然后把属于该直线的所有点对全部标记即可。

虽然做法很简单，但是因为码力衰弱，模拟的时候还出了几个 bug，这题写完时已经快 $9:30$ 了。

C 题

这题是傻逼题，不是指题目傻逼，而是我傻逼。

想法很简单，对该数分解质因数，因为看见这个数据规模高达 $10^{16}$ ，决定采用线筛（事实证明线筛是没有必要的，最暴力的分解方法就可以，毕竟是离线的），最傻逼的事情出现了，我写个线筛写出了这种狗屎代码：

for (int i = 1; i <= n; i++)
{
    if (!isprime[i])
    {
        prime[++cnt] = i;
        for (int j = 1; i * prime[j] <= n && j <= cnt; j++)
        {
            isprime[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }

}

错哪就不必多说了，反正考场上我死活没发现哪里错了，手推线筛也推不出来，耗了 30 多 min 还是决定改回埃筛了，分解质因数结果如下：

$$2021041820210418=2 \times 3 \times 3 \times 17 \times 131 \times 2857 \times 5882353$$

其实接下来的事情就很容易做了，两层 DFS，然后去重完事，但是因为之前的线筛傻逼问题，整得心情很差，不想处理去重这类问题，所以最后没写。

搞完这题时，时间已经来到了 $10:20$ ，我终究还是太菜。

D 题

建图，然后跑最短路完事，我用的还是 $Dijkstra$ ，尽管这么小的数据规模用 $Floyd$ 随便跑（我是傻逼）。主要问题在于我不好造数据来测试自己的最短路有没有写挂，要是写挂了，因为这是填空题，那就 gg 了。 这么看来，洛谷的最短路模板题给的样例数据质量还是不错的。

E 题

哈密顿回路计数不记得怎么写了，就先跳了。

最后半个小时回来写了个暴力，发现 $n=15$ 时已经要跑 $11s$ 才能跑出结果， $n$ 每增加 $1$ ，时间复杂度增加一个数量级这样，题目要求 $n=21$ 的结果，那还是算辽，跑不出来告辞。

F 题

第一道编程题。

乍一看以为是 NOIP 2018 D1T2 的货币系统，可以用类似 $dp$ 的方式标记所有可能的重量，这题多了个减法的要求，所以需要稍微处理一下防止同一个砝码使用多次。

G 题

博弈论不会写。主要是因为我不知道什么样的策略算最优，又没有部分分，就不写了。

H 题

比较有意思的题，第一次听说所谓“左孩子右兄弟”的构造方法。一开始没看懂题，看了一下样例才懂。赛后我同laybxc解释样例的时候使用了如下例子：

稍微思考一下就会发现，最优的构造策略是，对于每个节点，把深度贡献最大的子节点放到左子树的末端就可以了，这样每个节点的贡献就是：

$$子节点数+贡献最大的子节点的贡献$$

写法有点类似树链剖分，两次 DFS 可以统计出答案。

I 题

记得这种题见过不止一次，但是这次确实不会写了。思考了几种算法，大多是 $dp$ ，但是形如 ))))((((((((( 这样的样例依然没有想到一个很好的办法处理。

F 题

没时间了，题目也没看，虽然有部分分可以骗，\。

赛后

其实考试的时候我一直看的是机房电脑的时间，但是它比实际时间慢 10min，所以我以为是 $12:50$ 的时候就突然收卷了，虽然我已经写完了。

期望得分 $55$ 吧，主要是今年蓝桥杯画风也挺鬼畜的，有 NOIP 2018 的感觉了，填空题还是挺刺激的，如果以后有机会，来打打也不是不行。

回校的路上和GoldenPotato对了一下答案，填空题我写了的部分都是一样的，感觉还行，不过赛后期望分数和赛前期望的分数相比差距还是不小的，毕竟低估了比赛难度。

最终得了省一，还是相对满意的，不过似乎被其他学校暴打了，尽管这次比赛哈工大只来了 $3$ 人——我，GoldenPotato，和另一位未知老哥。好在 $300$ 大洋没被浪费。