abcdeffa's Blog

当局者迷,旁观者清。

0%

CSP2020 游记

今年的 CSP 终于不是在校运会期间了。

赛前去小卖铺欢乐购物。

CSP-J

感觉这回的 A 难度比上一年的高,但显然是一个二进制拆分,读完所有题以后写了切掉了。

B 题在读题的时候看到 $n \leq 10^5$ 懵了一小会。自闭了一段时间后觉得普及组不至于考高级数据结构,于是又读了一遍题,发现值域 600,那没事了。写了一下发现过了所有样例就丢下没有管了。

值得一提的是 A 题还是 B 题的一个样例输出末尾有两个换行,于是我手动修改了样例输出以通过 cmd 的比较。

然后看到 C 题有表达式的转换,直接弃了先去做 D 题。

想了一个用若干条向上的路径将一些向右和向下的机场连续路径段拼接起来的做法,但是这样朴素 DP ,即用前缀(?)和优化 DP,是 $O(n^2m)$ 的,过不了。

于是把朴素 DP 写出来了以后就考虑优化。

打了个表发现这个好像是可以用决策单调性优化的,然后就写了,和暴力拍了十几组以后发现没问题就拼在一起保存了。

这个时候已经是 10:00 左右了,但感觉还是有希望 AK 的?

然后去写 C,手玩了一下样例 2 成功地复习到了表达式的转换方法。然后就是建表达式树并乱搞了。

考场上口胡了一个做法,脑补了一下觉得是 $O(n)$ 的就丢下不管了。

过了大样例以后就不管了,觉得自己能 AK 了就在那里吃吃喝喝半小时,期间检查了十多遍文件。

出场后后悔考场上没有玩小恐龙(

出场后交流讨论,发现自己 C 题没记忆化而且做法的复杂度很有可能是假的,心态大崩。

CSP-S

开场看到 A 就不想写,读了 B,感觉好像有点神仙。

读了 C,感觉有趣,但我不会。读了 D,博弈题,有趣,但我不会。

写了一个小时的 A 以后看到自己过了所有样例,就丢下不管了。

然后发现这个 B 很 Simple,写了过了所有样例就不管了。

然后对 C 的部分分有点想法,但是觉得 D 更加可做然后就去做 D 了。

然后手写了两个堆,写了 6k+,调了极久以后过了前两个小样例。然后测大样例,发现答案差的有点小多,然后自闭了一会以后改了一下,发现和大样例有几组数据的答案差 1。然后各种乱改,始终没有过,奋战到最后随便保存了。

中途去写了一下 C 题的暴力,拿到了 20 分的好成绩。

后记

顺便说一下,提高组考完出考场以后遇到蛇了,好可怕。

A 题在出题人的生日那里判错了,改了一个 Byte 以后 60 -> 100,真是快乐呢。

B 题测了 4 个民间数据,没有一个是过的,结果在官方数据下过了……开心!

D 题居然还是可以拿到 $n = 3$ 的 20 分。

赛后改题,发现我普及组的 C 没有考虑有连续的多个非运算的情况,我以为没有这种情况的(

如果我发现了也许 C 题就 95 分了……但这并没有什么用。

赛后改提高组的 D 题,发现我的堆写错了一个 Byte,并且我没有意识到修改是保存的……

改完以后通过 O2 优化 A 掉了。