最后一舞

· · 生活·游记

最后一年了,之前的 CSP 游记写的都很简陋,今年贯彻一下这个风格好了。因为去年的 csp 很简单,但是我被卡常了没有 ak,所以今年本质是冲着 ak 去的。不过经过去年 noi 的大惨败,我已深刻认识到其他人出了 noi 就是演,所以其实也没那么关系 csp 的成绩——欺骗性太强。

考前感受一下,依旧是南广场排队。只是环顾四周已经没有什么认识的人了——最初和我站在一起的人,都已经金牌,有许多人选择不打了。不过还是有一些认识的同学的,考前我没怎么说话,我发现这样可以平复一下心态。

进场,打了一个快读头文件就趴下来睡觉了。我机房里似乎有一个我认识的 nfls 小朋友一直在敲键盘,可能是在写什么复杂板子,很厉害。

几乎是准时的下发了密码,Oct31==Dec25? 是经典老笑话了,好像是刚学进制转换的时候就讲过(八进制31=十进制25,所以万圣=圣诞,赛后发现竟然真的有人没看懂?)。

学习了一下平常模拟赛的打法,先读了一遍四个题。crystal 读完就会做了,subway 晕晕乎乎,不知道想要表达什么,先跳过了,migrate 看起来是不纯种计数题,可能需要 ds,hub 看起来是个很可做的 ds。

先花了十分钟写了一些 crystal,由于刚睡醒还调了两下。接着仔细阅读了 subway 题面,发现这个 w 是滚木,并且本质是关键点最短路,这我熟啊!这不是那个我出的 CF1869B 的原来版本吗,随便写了一下就过了。

这里还犯了一下唐诗,我以为 qd^2 是 4e8,所以感觉可能需要一定卡常,不过写完呢一测直接飞起来了,就没管了。前两天一交流我才知道 qd^2 是 4e7,有点搞笑。

然后我先去想了一下看起来更可做的 hub,发现只有一个连通块时根据 JOISC2019 关键城市 的经典做法,应该先选直径中心然后贪心选,那么两个连通块就是断一条边分别做,就有了一个 n^2 的做法。感觉套一个二分,然后做一些类似换根的东西是不是就可以做了?此时感觉不是很难,于是先不着急写,回去做了一下 migrate。

这个 migrate 首先快速得到了如何判定(使用 USACO Tractor Path 类似的做法),然后发现实际上只可能在一个位置错开一位,那么枚举这个错开的位置,左右 DP 合并一下即可。先实现了一个 O(n^2),没怎么调就过了大样例,接着本来想要写 vector 二分,后面发现可以用双指针改成了 O(n),于是一步一步改就过了大样例。此时大约 1h30min。

那还剩下大把时间,肯定是要冲一把 t4 的。我先得到了一个换根的假做法,花了半小时写出来发现样例过不去,然后去上了个厕所冷静一下,发现这个做法要上好多好多毛毛虫火箭才能做到 \log^2,感觉不是很值得,于是继续想 \log。想到剩下一个半小时,感觉自己就算会了也写不完,所以紧急开始拼暴力,先把 n^2 写了,然后打表找出了特殊性质的规律,然后写了个超级大的换根做了 k=2。所有大样例都是一遍过,此时理论 70。

本来打算拍一下,因为一看这个 t4 大样例就不强。但是我还是想要努力一下 ak 的,至少嘴巴 ak,于是继续在思考一些神秘做法,但是最后好像也没拿下。

一站起来听到同机房的学弟说他 385,妈呀,直接被吓哭,难道 t4 真的是可做题?

出来交流了一下,wzf 说他 t4 拍了一万组拍挂了,感觉根本不会卡。妈呀。

到家一水群,发现好像 370 还行不算低,遂睡觉。

出分在一个平凡的模拟赛下午,我没挂,但机房里有不少人 t4 的暴力挂了。wzf 的假做法确实没卡,mhb dyf ak了,感觉 nfls 过几年要称霸了。

最后一舞虽然没能完成我 ak 一次的愿望,不过也算中规中矩,保住了晚节,我很满意。希望 NOIP、省选、NOI 也能不演一次。