题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

· · 题解

可能场切了吧……就当我场切了吧。

手摸一下，发现不合法的充要条件为，存在一个 w=2 的数 x，选到他之前的时候恰好花费了 m-1，并且在其之前有一个 w=1 的数价值为 y<x，在其之后还有一个 w=1 的数价值小于 x-y 或者在其之后全都是 w=2 的。

考虑枚举这个 x，然后想如何让其之前恰好花费 m-1，不难想到，原来就先于他的数操作后仍然先于其操作，并且会使消耗加一；原来不先于他但是先于 \frac{x}{2} 的数，操作后会使消耗减一。因此相当于两部分选出来的数差一个值，范德蒙德卷积一下就可以 O(1) 计算。然后再考虑在 \frac{x}{2} 后面的部分，不妨枚举首个 w=1 的位置，那么其之后状态一定，其之前任意，方案数是简单的；再预处理一部分东西就可以做到严格 O(n^2) 了。

结束了……