CSP-S 2020 游记

2020-11-08 21:36:34


day -1 ~ day 1 上午

不顾一切,开始复习所学知识,发现自己要么没学,要么遗忘得差不多了,慌得一批……

于是开始疯狂敲模板,自认为自己是奋斗的模范(考前抱佛脚的模范?)

心里默念“一定要考我复习的模板,一定别考我没复习的模板”,只能祝自己 RP++

day 1 下午

考试前

13:00 左右,早早地赶到了考场,仍不死心,继续复习

13:40,经历了一小番波折,总算拿到了准考证,进入考点,然后去看了一下座位号,我竟然是某个区的 $1$ 号???这是否意味着今天能一马当先,一往无前,一表人才,一鸣惊人……当然是做白日梦呀

14:00 左右,拍集体照,口号都是 AK 什么的,算是活跃了一下气氛吧

14:15 左右,总算要进场了,再念了一波 RP++ 就进去了,也没落下什么东西

考试中

一坐下来就开始检查硬件设备,顺便把快速输入输出的板子敲了,没啥问题。考试前 $5$ 分钟解压试题包,算是很良心了。

依照惯例,T1 肯定是个签到题,读了一遍题把自己吓蒙了,一上来就大模拟?还能不能签到呀?

鼓足勇气开始敲,中途发现没水喝,想要找监考老师要瓶水,转念一想,敲完这道题再喝水。在缺水的威胁下(雾),我成功在 15:40 左右过了 T1 的大样例,并找监考老师要了瓶水,感觉时间不太够啊(慌)。

看了一眼 T2,觉得是道水题,怕想简单了而多读了几遍。在确定了这是道水题的情况下,松了一口气,顺便看了 T3 和 T4,最终决定先做 T2。

在付出巨大努力后(雾),总算在 16:30 左右过了 T2 的大样例,这中间想到一个坑点: $2^{64}-n$ 会溢出,把它特判成了 $2^{63}-n+2^{63}$,自以为这能坑掉一大堆人……(怎想到坑还没完,自已也被坑了)面对不久前发放的“糕点”无动于衷,便开始思考 T3。

似乎想到了解法,开始写代码,渐渐发现自己写不出来,还突然证伪了这种解法的时间复杂度,慌了起来。决定去上个厕所,回来把思路重新理一遍,有信心能把 T3 AC 掉。

回来想了想,总算意识到了这个拓扑排序的重点--先打标记最后下放,立马开始写。中途发现时间有点紧,加了加速,总算过了第一个样例(本人记性不好,不知道是几点)。但是发现第二个样例就过不了,就开始调,最后调出来一大堆 bug:

  1. 类型3函数可能会调用编号比它大的函数,如果在读入时直接处理它会挂

  2. 最后拓扑排序明明应该用之前预处理好的数组(vector),却用成了读入函数调用关系的数组(vector)

  3. 有的地方把类型 1/2 函数也连了边,最后拓扑排序的时候却不是这样,导致很多点压根没进队列

过了大样例,虽然已经 17:45 左右,不过调了这么久反而让我安心,这道题肯定不会写挂!(这预示着 T1 和 T2 会挂……)

最后就冲一冲 T4 的部分分,发现 20 pts 出奇的好拿,决定先写,却发现过不了样例。仔细一看,“11 14 14”,说好的以不降顺序排列呢?等等,我人傻了,这就是不降啊……赶紧把 a[1]-a[3]>a[2] 改成了 a[3]-a[1]>a[2],过了第一个样例,松了一口气……

然后忙着冲 $n \le 10$ 的 20 pts,也没检查 $n \le 3$ 的 20 pts,觉得这难道我还能写错?(之后啪啪打脸)最后发现这 20 pts 没搞出来,运行样例它 RE 了……

最后 7 min 检查了一下文件问题,发现 T2 的 bool 数组原本一个应该开 $c$ 大小(这一点很多人其实用的是 map 或离散化,但这样节省时间,反正数组开得下,空间也够),另一个应该开 $k$ 大小,结果都开成了 $c$ 大小,其实按照我之前算的空间,就算这样也就 $180 MB$,但怕空间算错还是改了回来。

最后一身轻松地走出考场。(这似乎预示着之后的反转……)

考试后

跟同校的同学讨论了一下,似乎我的做法没啥问题,我自认为过了大样例心里还是有点底的。

吃了一顿火锅,回家已经 21:00 多了,发现洛谷上只有题面,还没有民间数据,心想明天早上应该就会有的,看了一眼 CSP-J 的题,发现难度还 OK。

day 2

上午一起来发现民间数据已经上传,决定默写一遍拿来自测。

结果发现了 T2 的坑点,心想也就 5 pts 吧,还能怎么样?

后来发现 T3 过不了???T4 也只有 15 pts???

最后发现 T4 应该是 a[3]-a[1]>=a[2] 呀,因为一开始我以为是 $a_1 \ge a_2 \ge a_3$,那么一开始最强的蛇一定不会让次强的蛇变得和它一样强,但事实上是 $a_1 \le a_2 \le a_3$,那么它只需要不比次强的蛇弱就可以了……(20 pts 没了,心里好难受)

经讨论区一提醒发现 T3 $n$ 和 $m$ 有两个位置写反了,却过了大样例???开始担忧考场代码是否写错……

这么下来,我默写自测的结果是:

洛谷:100+95+100+15=310

牛客:100+95+100+0=295

结果晚自习回到机房,才发现教练早已在群里发了考场收的代码,于是开始评测,让我连连吐血大跌眼镜:

洛谷:40+95+100+15=250

牛客:60+95+100+0=255

原来是判公元后的年需要 ++ 时,在算了 4 年周期之后就立即执行,导致如果是公元前 1 年,但答案是公元 1-3 年,代码会算成公元 0-2 年……结果我默写的时候把这点写对了……

晚上合眼前,突然想起 T1 时间复杂度也不太对,明明最后是一个二分查找的板子(用 lower_bound 即可),结果我却直接铁头功,搞得时间复杂度上界为 $O(4800Q)$(从 1600 年起,我是以 400 年为周期)。只能相信 CCF 的机子能跑过 $4.8 \times 10^8$ 的 if 语句了……

这么说来 T1 的后 60 pts,和 T4 的前 20 pts,就仰赖 CCF 的数据了,到头来还是考验 RP 呀……

day 3 - 总结

这次丢了很多不该丢的分,今年 CSP-S 真就是有人说的:

比谁会的多 (×)

比谁挂的少 (√)

T1:真的是错了很小的一个细节,看来大模拟写少了呀!并且 lower_bound 竟然没想到,暴力铁头功……我像是退化成了第一次参加 CSP-J 的萌新……

T2:去年坑 unsigned long long ,没被坑;今年又来,直接用 $2^{64}$ 把我坑惨了……长记性了,一定注意极限数据范围!!!

T3:中途那次理清思路做得很好,一定的调试能力救了我一命,这也是这次唯一 AC 的一道题呀。

T4:20 pts 打挂了……事实上这是我的老毛病,上次月考时就是改错不彻底,白白丢掉了一些分数,属于好不容易发现了错误,却没改彻底,功亏一篑。所以一定要记好:改错要仔细,不要改了一个就开跑!!!另外看网上的游记和洛谷自测排行榜,发现有很多人觉得 70 pts 很好拿???反正我在考场上没有一丁点思路……应该有两点原因吧:

  1. 这样的题练少了;

  2. 总体来说时间分配不够合理,虽然没像一些选手一样对着 T1 刚 2h,但还是没给后面的题留足时间。

总体来说,还有一个非常严重的问题,因为这次时间较紧,有点慌张,所有题均未进行对拍或手造数据验证,大样例又是脚造的, 一定程度上导致了 T1 和 T4 挂掉的结果,这一点平时训练就要练起来,NOIP 不能再栽在这上面了!

最后留下总结中的总结:模拟靠码力,边界要处理,思路要清晰,调试要犀利,改错要彻底,时间分配要合理,手构数据才安心!