四年磨一剑——NOIP2025游记

Lysra · 2025-11-28 18:13:05 · 生活·游记

Day 0

早上跟 zsj 来到机房，讨论了几道最近做过的题。

中午乘长途车来到南京，熟悉的维也纳酒店。

然后车上把电脑密码忘了，什么都干不了，睡了一车（

酒店跟 yzy 一起住神秘的 8339 房间，ljn 跟来一起玩 UNO 了。

UNO 还是太好玩了。ljn 这个汤比一直说什么“我通过他眼睛的反射光判断出这张牌不是 xx 牌”，没一次说对的（

还有次转黄只剩一张了，结果几个人他妈一起出红牌硬是把我的转黄给否决了，罗马共和制 UNO 是吧（

然后玩了接近 2h 的掼蛋，一开始一路赢到 A:2，以为马上就结束了，结果断断续续输了五六把，直接平成 A:A 了。

最后焦灼地战斗了近半小时，还是输了，可能一晚上睡不着了/ll

吃晚饭，两包泡面还是太丰盛了。我让 yzy 去烧水，烧了一会儿后直接就往面里倒，倒完后就听见 yzy 说这是洗烧水壶的自来水。

哈哈，这个世界疯了。

Day 1

熬到一点半睡了，看了一些板子。

早上被 yzy 电话手表连续十个闹钟吵醒，下楼吃饭。

从维也纳酒店出来，挺感慨的，一个酒店陪伴了我四年半。客车上发现 ljn 还在对着蓝书内卷，看了一圈发现就我啥都没干，有点慌。

进考场，103-047。

明显感觉到自己手都在抖，鼠标都握不稳。四年的付出用一场比赛来验证，还是太残酷了点，如果还发挥的像 CSP 那样就真的没法给自己的 OI 生涯一个交代了。

试机时间很充裕，打了线段树，强连通分量，树剖。看时间差不多了就等密码。

提前五分钟下发密码好评，成功在开赛前想出 T1，并在开赛 5min 后跑过所有大样例。

不放心拍了几组，发现没问题就放了。现在想来幸好自己没犯什么唐，这个 T1 大样例真是水到没边了，不判没有单个和不判前缀小于 m 竟然都测不出来。

有理由怀疑 CCF 是故意规避这些情况去坑选手的，因为随便拍几组数据都能把这个测出来，很难评。

做完之后上了个厕所，把后三题看了一下。

T2 计数，T3 神秘高次方 dp，T4 神秘 ds。

当时还是很庆幸数数只放了 T2 的，看到 T4 竟然是纯 ds 也挺惊喜的，毕竟赛前就一直在做 ds。

然后就是对着 T2 大战 45min 无果，当时心想完了全完了，难道 CSP 考场的一切将要在 NOIP 重演吗......

果断弃掉 T2 去看了后两题，T3 设计出一个 O(n^6) 的幽默 dp，正确性很对但很难打。后来又花了一会儿猜了个结论，也就是子树中的权值连续，这样就能从幽默的 O(n^6) 优化到幽默的 O(n^5)，考场上没绷住直接笑出了声，认为自己的 OI 就要这样草草结束了。

看 T4，O(nq\sum\text{len}) 的做法是显然的，怒砍 15 pts，拿到 T1 后的第一桶金。

后面看了看 BC 性质和 n=3000 的档，没什么思路就放了。

继续想 T2，实在想不出来就拼好分大战吧。

然后就发现自己好像会了，做了一个初步 O(n^3) 的东西。肯定是要优化最里面一维组合的，但我不会组合意义和恒等式啊/ll

但当时灵光一现做了一个部分预处理后整体计算的优化，把里面一维近乎优化到常数复杂度了。

花了半小时边调边打写出了一份代码，一测大样例全不对。

后来发现自己求组合数上界写错了，改过来后第二个大样例就只错几个地方了。

然后就是无脑模拟环节，把错的样例拉出来疯狂手玩，结果发现手玩出的也是错误答案。

也就是说思路错了，考试时间还剩 90min，当时慌得一批。要是错的离谱可能真就 100+eps 分离场了。

后来一直在犹豫要不要花一会儿写个暴力跑一下所有结果，然后他妈发现暴力的难写程度跟正解有的一拼，写了一半还是打算继续手玩。

然后总算在还剩 1h 时顿悟了，原来最左侧是可以瞎选的啊，之前一直把 2^x 乘成 x 了，这竟然能把大部分数据跑过去，煞笔大样例。

调试又饭堂调了一会儿，发现自己最后 n=5000 的点要跑接近 20s，根本过不去。

草他妈的 8pts 谁爱要谁写去，出题人是要思多少浮木才会想出光速幂卡快速幂这种东西啊。

还剩 40min，太棒了这下 T3 O(n^6) 都没时间打了，再去看 T4，发现自己竟然会了一个莫队套超级钢琴的 O(q\sqrt n\sum\text{len}) 的做法，能把 BC 都草过去，但只剩不到半小时了。

疯狂打了 2k 后还剩 15min，意识到这东西是不可能打完了，滚去打 T3 招笑 O(n^n) 做法了。

最后 5min 用点小性质优化到了 O((n-2)^{n-2})，但还是跑不过 n=13。

那就这样吧。