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

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

赛前

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

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

比赛日

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

题面

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

A 题

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

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

好像几分钟就秒了这题。

B 题

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

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

C 题

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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×3×3×17×131×2857×58823532021041820210418=2 \times 3 \times 3 \times 17 \times 131 \times 2857 \times 5882353

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

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

D 题

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

E 题

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

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

F 题

第一道编程题。

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

G 题

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

H 题

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

gEgw6O.md.jpg

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

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

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

I 题

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

F 题

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

赛后

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

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

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

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