NOIP 2025 游记

· · 生活·游记

开了 T1，自认为是很唐的贪心然后喜提 Wrong answer on pretest 6，然后想了一会加了个特判过掉了希望没有别的问题，此时已经过去了 30min。

开了 T2，设法推了一个 O(n^{3}) 的做法，发现直接上范德蒙德卷积就少了一个 n，于是着手实现。结果实现的时候，一个本使用指针就可以解决的东西我选择使用 lower_bound 实现导致最后两个点直接趋势。10:10 的时候获得 Wrong answer on pretest 2 发现平均每八个点就有一个答案少一点，我怀疑式子推错了结果改了 50min 越错越多，心态肥肠炸裂。

11:10 T3 胡了一个 O(2^{n}n) 的状压做法混了 24pts 决定回去继续看 T2，然后发现我原来的式子是对的，只是一个循环的上界少了一。当时（11:40）改完 pretest 就这么过了的时候我整个人都傻了。

继续回去看 T3 通过感性猜测发现好像其实可以不用状压然后在 12:10 实现了 O(n^4) dp，尝试去掉一个 n 然后挂了没心情调就放弃赶 T4 暴力去了。此时已经 12:25。

T4 口胡了一个 O(qn^2) 的做法可是只有 15pts 然后发现特殊性质 AB 可以直接套用于是就稍作修改混了 40pts，然后就结束了。