zhaoyp 的博客

zhaoyp 的博客

CSP2020 游记

posted on 2020-11-08 22:00:49 | under 游记 |

DAY 0

在动车上,打了各种背包,最短路还有一些奇奇怪怪的板子,结果发现自己连 SPFA 都不会打了,顿时感觉要凉。

路上都没有遇见同校的dalao,RP-- 暗示了什么

不过住宿的地方离学校很近,只有一个红绿灯,两三分钟就能到。泡了碗面就草草睡觉了,有一丝不好的预感。 疯狂暗示

DAY 1

CSP-J

8:15 到了考场,上了个厕所之后刚好开始解密,瞥了一眼同位置提高选手的准考证,发现自己被单调队列了,感觉自己好菜。继续暗示

先开 T1 发现不能一眼看出答案,决定先打一个 $80pts$ 的做法,DFS 枚举一下指数,然后过了两个小样例和大样例,发现之前的复杂度好像错了,应该能过极限数据,跑了一下 $10^7$ 的数据时间过了,但输出结果是 $-1$。

这时候已经过去了 $30 min$ 左右,之后去开 T2 ,完全没用意识到 T1 出了问题。

开始写 T2,打算是在每一次出新成绩之后对现有序列进行一次 sort ,写完之后过掉了两个小样例,但大样例被卡了,复杂度 $O(n ^ 2 \log n)$,只能拿到 $50pts$,后来想到由于每次操作之前的序列都是有序的,可以将 sort 改成, $O(n)$ 的插入排序,但好像还是只有 $50pts$ ,之后看到每个选手的成绩均为不超过 $600$ 的非负整数启发了我,可以做一个类似于桶排的操作,复杂度 $O(600n)$ ,一遍过了大样例,应该能A。

重新开 T3 其实之前刚开卷的时候已经看了,没搞懂样例,好不容易理解了样例 $1$ ,样例 $2$ 就不行了,之好放弃。

T4 看着很像DP,不过式子没推出类,也想过把题目转化为求最短路,还是不行,最后只打了一个 $20pts$ 的暴力,还调了好久。

此时还剩下大概 $1 h 20 min$ ,去检查T1,T2,脚造数据。

最后 $20 min$ 的时候,突发奇想用计算器看了下 $10 ^ 7$ 的二进制, 发现这题是个二进制位拆分,只有是奇数时才无解,回去找 bug , 结果发现是自己数组开小了,只开了 $80pts$ 的大小,改完之后只有 $15min$ 了,决定不再改了。

预估 $100 + 100 + 0 + 20 = 220$。

CSP-S

开场先开 T1 ,发现是个神仙题,T2 没多大思路,决定先写T1。

然后就开始大模拟,写了 1kb+,过掉了样例 ,花了将近 $2h$ 。

重读一遍题之后觉得刚才读的题是假的吧,这才是 T1。所有的 $q_i$ 互不相同,大大降低了难度。先打了一个 $O(nm)$ 的做法,拿到了 $60pts$ ,之后发现由于许多 $p_i$ 都是相同的,浪费了许多时间,可以直接枚举 $k$ 位,复杂度降到了 $O(nk)$ 。

T3,T4都没有思路选择放弃。

出考场之后才知道 T2 爆ull,应该会挂掉一个点。

预估 $[50,100] + 95 + 0 + 0 = [145,195]$。

分数

CSP-J: $100 + 100 + 0 + 25 = 225$

CSP-S: $100 + 60 + 0 + 0 = 160$

在动车上

回去的动车上遇到了cjz,发现pj T3 随便用一个栈模拟一下,再加个特判就有 $50pts$ 了。

DAY 6~7

不出意料,期中考挂了。