NOIP 2025 爆炸记

· · 生活·游记

Day 0：

考前一天写了猪国杀和双序列扩展。

Day 1：

进考场，背后是 max0810，感觉要被补集了。

开场看 T1，发现如果一个物品要买偶数次的话一定不如买同意次数的 x + y 的最小值 sum，于是其它物品只会买一次；考虑 x < \frac{sum}{2} 才有买的必要，于是先把 x < \frac{sum}{2} 的全买了，然后反悔贪；最后剩下的去买其他的即可；40min 写完。

然后通读所有题，怎么构成和去年好像，T1 greedy，T2 counting，T3 tree，T4 ds。

于是猜测 T2 难度和去年差不多，应该是人均题，虽然题意有些复杂，但是果断开冲。

手摸一下，猜测不合法应该是什么，最后剩下一块钱，第一个买不起的是 pos（显然价格是 2），上一个用一块钱买的是 lst，最后那一块钱买的是 now，当 a_{lst} + a_{now} < a_{pos} 时不合法。

写了下 2^n，发现能过前三个大洋里，然后考虑优化；就是枚举卡着买不起的物品 pos，将所有物品分为三类：

然后考虑上一个 w = 1 的位置，如果它上面都是第一类，那直接枚举 lst 然后就可以很简单的算。

否则有第二类物品，显然上一个 w = 1 的位置一定是第二类，枚举它，然后这个两侧的方案应该是范德蒙雷卷积形式的。

后面还有个 2 的幂次，然后过程中走个双指针找一下分界点；然后 a 相同的还有些细节。

然后开始写 + 调，耗时 3h，最后大洋里有 eps 行 WA，都比较大，根本调不出来。在调的 3h 中，中间花了 1h 去做 T3, T4。

T3 想到之前看的一个 MEX 延迟钦定的题，于是定义了状态 dp_{u, i, j} 表示子树 mex = i 且 >i 的位置有 j 个还没有确定的最大权值，转移就是背包型的，时间复杂度是 O(n^3) 或者 O(n^4) 的。

T4 是一个数据结构，虽然我比较擅长这种类型的题（去年靠 query 翻了点分），但是想到 T2 可能被切穿了，确实不太敢深入做了；于是随便打了点暴力。

结束了，爆炸。

总结一下：