NOIP 2025 爆炸记

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

进考场，背后是 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 可能被切穿了，确实不太敢深入做了；于是随便打了点暴力。

结束了，爆炸。

总结一下：