NOIP2020 游记

2020-12-06 18:23:19


8:20

看到压缩文件里有个 string 感觉非常慌,因为我字符串啥都不会。

8:25

老师写解压密码,解压完马上去看了一眼 T2,秒出 $O(Tn(\log n+26))$ 做法,好像有 84,想了一下觉得非常对,准备之后写代码,然后直接扔了去看 T1。

发现 T1 是拓扑排序板子。

8:50

T1 写完了,成功没有过样例,调了一下发现拓扑排序挂了,然后过了前 2 个样例,第 3 个没过,看了一眼输出好像是溢出了,瞎改了一下就过了,看了下数据范围,感觉最大出现的数是 $60^{10}$,算了一下大概是 $6\times10^{17}$,不会炸 long long,就没管太多了。

然而赛后发现极限是 $60^{11}$,无了。

9:30

T2 写了双 hash,一遍过了所有样例,扔了去看 T3。

不会吧不会吧,NOIP 怎么出构造题了,怎么发 spj 了。

大概花了 30min 口胡了一个做法,然后随便手玩了几组数据就挂掉了,感觉这个题非常不可做,就去看 T4 了。

10:20

只会 T4 的前 40 分,准备打完跑路想 T3。

前 30 分一遍就过了能过的样例,后 10 分没有数据就手动和前面的暴力对拍,然后什么数据都挂,调了 15min 左右,终于过拍了,重新去想 T3。

11:00

2 小时一个 T3 你能秒我?你能秒掉我?你要是今天 T3 把我秒了,我当场【数据删除】。

大概又想了 30min 胡了一个新做法,手玩了一下发现不大行,然后瞎改了一下策略的细节发现手玩没什么问题了,但是完全不知道这样的做法移动步数是多少,想了想反正也没啥事可以干,就先写了一下。

12:00

写完了自己口胡的做法,一测样例死循环了,可是手玩样例是没问题的,感觉必然是实现挂了。

12:20

发现写了一句 flag=flag&&work(i),flag=0 时不会执行 work(i),,感觉自己是个 sb,改掉就过样例了,然后跑了一下大样例,生成了输出文件,

然后打开 cmd 试着编译 checker 然后出一堆奇怪的问题,我看不懂,然后把 checker 拉到桌面上就编译成功了,不知道为啥,按题面使用 checker 后,checker 过了几秒后打印出 $\color{green}{ok}$,然后点开输出文件看了看步数,竟然只用了 14w 步,比期望要少,挺开心的,

然后随了一组 50 85 的数据测了一下,用了 17w 步,这大样例怎么连随机数据都不如,

直接随了一组 50 400 的极限数据,一看用了 110w 步,显然是没了,50 300 的随机数据用了 75+w 步左右,感觉可以拿 70 分。

12:30

完全不会优化 T3,自闭,本机跑了一下 T2 的随机极限数据,跑了 1.7s,然后极度求稳把双 hash 改成了三 hash,跑 1.9s,我也不知道自己为啥要这么干。

12:35

检查了一下之前的代码,把 T1 全部改成先除后乘了。

继续想了想 T3 还是不会,然后一直自闭到结束。

13:00

结束了。


刚出来估分 100+84+70+40=294,

发现 T1 要写高精,于是:

(80-100)+84+70+40=274-294,

发现 T2 有微小的概率能卡过,于是:

(80-100)+(84-100)+70+40=274-310,

希望不要 FST,

希望 T1 不卡 long long

希望 T2 能卡过去。

luogu:

90+96+65+40=291,

XJ:

90+84+70+40=284,

oitiku:

100+84+70+40=294。

T3 在 luogu 挂了,似乎出了点大问题,于是现在自己估分:

(80-100)+(84-100)+(40-70)+40=244-310。

官方成绩:

90+84+80+45=299,

第一次反向挂分,感谢 CCF。