NOIP2025 游记

· · 生活·游记

第一次写游记。

8:30 开考。

开场 1min 会了 t1，写完过了前三个大样例，第四个挂掉了。

瞪了 5min 发现做法假了，需要枚举选多少个奇数，修了 5min 通过大样例。

非常自信，开 t2。觉得正难则反，先想了 30min 刻画不合法方案，想到一个 3 次方做法。为了防止自己脑子糊涂，先去了趟厕所。在厕所踱步了一会，回来时是 9:30，想着 1h 了不能啥都没有，先写 40 分算了。

写好调了一会，调完是 10:10。接着想优化。花了 10min 想到了除去范德蒙德卷积以外的所有优化，并一边测样例一边改，改完了紧接着 10min 啥思路都没有，隐隐约约记得范德蒙德卷积的优化式子，但实际上忘了。

10:30 了，我带着 “做完后两题回来脑子热了就能秒了” 的心态开了 t3。

t3 1h 只得到了 a_i>a_{Son_i} 的结论，然后还是啥也不会，中途还写了个假做法，意识到假掉的时候已经 11:30 了。心态有点崩，去了趟厕所缓了缓。事已至此我已经深刻意识到不能再死冲正解了，于是我开了 t4。

t4 15min 获得了一个分治 O(nq\log n) 做法，然后惊奇的发现这玩意能直接再冲过去 ABDE 性质！然后直接开写。写加调 35min，在 12:25 通过所有大样例，只有 C 性质和无性质超过了 2s。C 性质懒得写，毕竟还不会 t2。

回去看 t2，对范德蒙德卷积推导了一下发现可以直接组合意义，变成一个组合数，那么就做完了。写出来测了所有大样例，只有 sale11 跑得飞慢。鉴于比赛只剩 20min，我决定直接扔掉最后 8 分。

最后 t3 写了最低档的 n4^n 暴力，拿了 8 分。比赛就结束了。

感觉挺难的，t3 感觉很 adhoc，而我显然没对上脑电波，t4 做法似乎扩展性不强，至少还不会正解，t2 被卡常了丢掉了 8 分有点遗憾。水平有待提高。