最后一舞
最后一年了,之前的 CSP 游记写的都很简陋,今年贯彻一下这个风格好了。因为去年的 csp 很简单,但是我被卡常了没有 ak,所以今年本质是冲着 ak 去的。不过经过去年 noi 的大惨败,我已深刻认识到其他人出了 noi 就是演,所以其实也没那么关系 csp 的成绩——欺骗性太强。
考前感受一下,依旧是南广场排队。只是环顾四周已经没有什么认识的人了——最初和我站在一起的人,都已经金牌,有许多人选择不打了。不过还是有一些认识的同学的,考前我没怎么说话,我发现这样可以平复一下心态。
进场,打了一个快读头文件就趴下来睡觉了。我机房里似乎有一个我认识的 nfls 小朋友一直在敲键盘,可能是在写什么复杂板子,很厉害。
几乎是准时的下发了密码,Oct31==Dec25? 是经典老笑话了,好像是刚学进制转换的时候就讲过(八进制31=十进制25,所以万圣=圣诞,赛后发现竟然真的有人没看懂?)。
学习了一下平常模拟赛的打法,先读了一遍四个题。crystal 读完就会做了,subway 晕晕乎乎,不知道想要表达什么,先跳过了,migrate 看起来是不纯种计数题,可能需要 ds,hub 看起来是个很可做的 ds。
先花了十分钟写了一些 crystal,由于刚睡醒还调了两下。接着仔细阅读了 subway 题面,发现这个
这里还犯了一下唐诗,我以为
然后我先去想了一下看起来更可做的 hub,发现只有一个连通块时根据 JOISC2019 关键城市 的经典做法,应该先选直径中心然后贪心选,那么两个连通块就是断一条边分别做,就有了一个
这个 migrate 首先快速得到了如何判定(使用 USACO Tractor Path 类似的做法),然后发现实际上只可能在一个位置错开一位,那么枚举这个错开的位置,左右 DP 合并一下即可。先实现了一个
那还剩下大把时间,肯定是要冲一把 t4 的。我先得到了一个换根的假做法,花了半小时写出来发现样例过不去,然后去上了个厕所冷静一下,发现这个做法要上好多好多毛毛虫火箭才能做到
本来打算拍一下,因为一看这个 t4 大样例就不强。但是我还是想要努力一下 ak 的,至少嘴巴 ak,于是继续在思考一些神秘做法,但是最后好像也没拿下。
一站起来听到同机房的学弟说他 385,妈呀,直接被吓哭,难道 t4 真的是可做题?
出来交流了一下,wzf 说他 t4 拍了一万组拍挂了,感觉根本不会卡。妈呀。
到家一水群,发现好像
出分在一个平凡的模拟赛下午,我没挂,但机房里有不少人 t4 的暴力挂了。wzf 的假做法确实没卡,mhb dyf ak了,感觉 nfls 过几年要称霸了。
最后一舞虽然没能完成我 ak 一次的愿望,不过也算中规中矩,保住了晚节,我很满意。希望 NOIP、省选、NOI 也能不演一次。