NOIP2020 游记

ShanLunjiaJian的NOIP2020游记

Posted by ShanLunjiaJian's Blog on December 6, 2020

Day -3,-2,-1

草草草体质不好的我之前天天集训累垮了?感冒了在家躺了三天。

Day 0

上午回去上了半天课,下午跟刀,zrz和赵神一起开车到了日照。在车上看了日颓智障题和拓扑排序。大约五点多到了宾馆,一起吃了晚饭之后回房间预习。

我就看了之前三天的模拟赛题,看了个《赛道修建》,然后学习了一下左偏树,然后十点半就睡觉了。

半夜有点冷,给我冻醒了……然后裹紧被子继续睡了。感觉睡眠比较充足。

奥利奥真是棒到不行——!

Day 1

早上六点四十起来,吃了草率的早餐,七点半从宾馆出发,七点五十进场。

进场的时候,监考老师问我,你这个袋子这么满,装的什么东西?

我说,水和咖啡,笔,药,还有奥——利——奥——!

8:30

开题,这个T1智障题,T2一时不太会做,T3构造可以一试,T4什么东西?

8:40

然后开始写T1,车上看的拓扑排序居然真的用上了……但是只开了long long

9:10

然后去看T2,想了十分钟发现不该枚举$C$,而是应该枚举$AB$,字符串Hash来判延伸,复杂度是调和数的那个$\log$,于是二十分钟打了个奇怪的东西过了大样例。复杂度$O(n(|\sum|+\log n))$,好像不太稳只能拿84pts,也没管。

模数选择unsigned long long自然溢出,基数选择质数$29$。信仰之力。

9:40

把咖啡拿出来干了。

这个T3好像很不可做,但是我发现可以很随便地用$4m$次操作交换两个东西,打了40pts部分分打算爬,结果发现checker编译不了?(我就直接在Windows Powershell里面输的指令,我也不太懂)于是手写个大模拟测了一下过了三个样例。

然后想了更奇怪的东西,比如想到了要排序,但是不懂怎么对每个栈先排好序,所以爬了。

11:20

回去看T1T2,发现这个T1好像能爆long long?并且确实构造出了一种方法。改成unsigned long long好像还不够,难道要高精?

算了一会再说,先康这个T4。

11:30

不过在此之前去趟洗手间?

这个T4满分好像也很不可做,跟前面根本不是一个算法?那我们考虑打个80部分分,然后想到让每个点一起走,每次如果有点出去了,出去的肯定是一个超面,所以剩下的还是超长方体,所以维护左下角右上角即可,然后大样例4s……

11:55

如果我可以让每一步都有点出去,那我总移动次数就是$O(\sum w)$,所以我打了个表,发现每一步 :

要么没有点会出去,要么第一次有点出去,要么每一次都有点出去。

所以把每个操作和它前面没用的压起来就好了。打了$O(n+k\sum w)$的80pts暴力,也没想着去优化掉那个$k$(按维度分别压就可以做到$O(nk+\sum w)$,或者瞎猜一小步就是$O(n+\sum w)$,当时没想)。

12:30

回去看T1,发现这个高精半小时写不出来。

于是开始重测大样例并反复检查freopen。

T2造了个全a的数据,跑了2s,感觉要没,但是也不会优化。

自己算了一下,最坏情况下大概有80+80+40+70=270pts?一般情况80+84+40+80=284pts,运气好可以得到90+92+40+80=302pts,看起来非常可观。

1:05

出考场,发现大家好像都觉得比CSP难?

见到了zzc老师,我说我估分284,他说很好。

见到了cjh神,他说光顾着T2,后面没怎么打。(应该是这么说的吧)

见到了刀,赵神和zrz,他们好像都不会T2 84pts ???

(此处省略我校十几人?)

没见到Pbri,她1:25才回我消息……

没见到任何一个网友。

1:30

上车回济南。赵神的父亲买了肯德基,但是他不知道我不吃辣的东西?于是那个香辣鸡腿堡吃了一口就装回袋子了,然后搞了两包薯条。

之后(也许OI无关?)

在车上看到各群都在讨论T1是不是只有1-m点入度为0,然后我忘了我是怎么写的了,感觉出题人可能又不想要马,这边已经骂上了,没想到这次出题人是要马的……这里给您道个歉!

晚上四家(当然是一起去的这四家)聚餐,聊了一些关于文化课的问题。那三位都是高一的老年人了,只有我还是中年人……不过我要是不搞文化课,不小的概率去不了高中部。

妈呀当时气死我了,我回来跟我妈说我都284pts了,搞个锤子文化课,我直接停五个月课冲省选,然后大不了爬去新航实验?

zzc老师要我那就保送我,不要我那我也对高中部没兴趣/shui

然后我妈说的就无关紧要了,这里不提。

学校教我们什么”好好学习不留遗憾”,我看进个E队才叫不留遗憾吧!

另外,居然有人不喜欢T3这样的思维题。我倒是觉得思维题很好玩。

Day2

Pbri上oitiku一康,我100+84+40+80=304pts,啊这

不过实际应该是294,T1没卡我的ull。

然后就没什么可说的了,谢谢大家坚持看完了几十行废话。下面是很无聊的东西了。(但是有写到官方成绩)

Day3

回去whk了。

下午足球赛,已经是最后一场了,前三场我光请假了都没上……

然后天巨冷给我冻成智障。回家吃完饭就累得躺在沙发上睡着了。

Day4

果然着凉了……早上起来就头重脚轻浑身没劲,又在家躺了一天。(天天请假班主任都有点生气了)

立个flag,下周开始锻炼身体……

中午起来看到sd出成绩了,还真就90+92+40+80=302pts,sd rk3¿

然后看到赵神说要退役,这是坚决不行的/kel

下午起来一看赵神还是斗志满满嘛。zsy yyds!