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

· · 题解

谁评的黑？何意味。不是很难，蓝 / 下下位紫差不多。 :::info[O(n^3) 暴力] 易得贪心出错时，某个 w_i=2 之前选的容量恰好 m-1，且紧挨着前面的 w_l=1 与紧挨着后面的 w_r=1 满足 a_l+a_r<a_i。

从大到小排序 a，枚举 w=2 的位置 i。考虑每个物品对于性价比 <\frac{a_i}{2} 的容量贡献：

·j<i 时 贡献 1 或 2。

·i<j\land2a_j<a_i 时贡献 0 或 1。

·2a_j\ge a_i 时贡献 0。

显然 l 在前两类且贡献 1，r 在第三类。

前两类共选了 $m-1$。 易得前两类贡献 $1$ 的差是个常数。 暴力地，枚举第一类选了多少个，然后组合数处理贡献，时间复杂度 $O(n^3)$。 ::: 考虑优化，双指针省不掉，考虑 $j=l$ 方案数大概长这个样子：（除了 $k$ 均为常数，$k$ 任意正整数） $\displaystyle \sum\binom{c}{k}\binom{d}{k+e}

这不就是 abc433f 变式吗！这个题 *1350 左右，下位 \textcolor{green}{普及+/提高}，典型且简单。依据：abc433f 900+ 人场切。不包括我

考虑把一个组合数选取的集合变成其补集，这样选的数差一定变成了和一定，然后简单组合意义即可。

\displaystyle \sum\binom{c}{k}\binom{d}{d-k-e}=\binom{c+d}{d-e}

做完了。