题解：P14636 [NOIP2025] 清仓甩卖 / sale

· · 题解

妈妈我场切紫了。

思路

合法显然不好求，选择拿总方案数减去不合法的方案数。

手膜样例可以发现贪心策略错误时仅当选到只剩 2 元时选择了一个更劣的 1 元物品导致不能选后面的某个 2 元物品，并且选择下一个 1 元物品也不会更优。

于是先将 a 升序排序，然后可以枚举被舍弃掉的 2 元物品和导致它被舍弃的 1 元物品位置 x,y，则后面选到的第一个 1 元物品 i 的价值 a_i 需要小于 a_x-a_y。于是对于 a_i<a_x-a_y 的物品可以选 1 元也可以选 2 元，而 a_i\ge a_x-a_y 的物品只能选 2 元。设 cnt 为 a_i<a_x-a_y 的物品数量，方案数即为 2^{cnt}。不减 1 是因为不选 1 元物品也是合法的。

再来考虑前面的物品，我们要求方案数使得选到被舍弃掉的 2 元物品时只剩 1 元。

对于 i<y 的物品 i，由于 y 要成为最后一个被选的 1 元物品，所以物品 i 只能定为 2 元排到 x 后面选。

对于 y<i<x 的物品 i，如果被定为 2 元，则会排到 x 后面选，否则在前面选，这里设 y<i<x 的物品数量为 k1，显然有 k1=x-y-1。

对于 x<i 的物品 i，可以选 1 元也可以选 2 元，这里设 x<i 的物品数量为 k2，显然有 k2=n-x。

由于选到被舍弃掉的 2 元物品时只剩 1 元，所以除掉导致它被舍弃的 1 元物品后价格之和应为 m-2。简单解方程可以发现当有 n 个物品，价格和为 m 时，2 元物品有 m-n 个。于是枚举 k1 中选择 1 元的物品数量，便可得到方案数为：

\sum_{i=0}^{k1} \binom{k1}{i}\binom{k2}{m-2-i-k2}

发现这是个范德蒙德卷积的形式（其实我上场 ABC 才知道范德蒙德卷积），可以化为：

\binom{k1+k2}{m-2-k2}

将前面选物品的方案数和后面选物品的方案数相乘即可得到最终答案。

找 a_i<a_x-a_y 的物品是 O(\log n) 复杂度的，但是可以指针优化，预处理组合数和 2^x，总时间复杂度 O(n^2)。