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

MPLN · 2025-11-29 14:59:36 · 题解

相信自己的做法不会有错，并不复杂。场上通过所有大样例。

首先统计是最优的肯定不好做，考虑统计不是最优的，然后用总方案数减去。

发现这种情况就是在只剩两块钱的时候，先选了价格 1 的物品 A，后面买不了价格 2 的，只能再选一个价格 1 的物品 B 或者没有能买的了。

这时候不一定最优，因为如果不选 A，直接就买一个价格 2 的物品 C 可能更优秀。

考虑枚举 A，设为 a_i。设 C 为 a_k，则要求 a_i>\frac{a_k}{2}，原因是我们在面临这两个物品的时候先选了 A（性价比高）。

先将物品排序，二分得到 k\in [i+1,p]。

接着枚举 B，设为 a_j，则有 j<i，且 a_i+a_j<a_k（我们要求其不优）。

现在要求预处理后，已知 i,j，可以 O(1) 算出方案数。

把刚才的不等式再拿出来：a_i+a_j<a_k<2a_i，发现合法区间变成 k\in [l,p]，l 可以双指针得到。

我们在枚举 i 之后，可以先枚举每个 k 对应的方案数，这里的方案数只考虑 [i+1,n] 的价格取值，由于已经知道 i,k，可以再结合一个性质推出各个区间有多少个 1 和多少个 2，这个性质就是：单独考虑价格为 1 或 2，选取的物品都是一个后缀。而显然，k 是从后往前第一个没选的 2。所以就很好算了。

设 k=x 的时候 [i+1,n] 的价格取值方案数为 cnt_x，则求出 cnt 的后缀和 suf_x=\sum_{t=x}^p cnt_t 即可快速得到 k\in [l,p] 的方案数总和。

接下来考虑 [1,i-1] 的价格取值方案（显然我们已经钦定了 i 填 1），在 [j+1,i-1] 中，必须都填 2，这样才能保证选完 A（a_i）后我们会选择 B（a_j），而在 [1,j-1] 中，填什么是无所谓的，所以我们的方案数就是 suf_l*2^{j-1}。

现在似乎做完了，但是还要考虑不存在 B 的情况（\forall 1\le j\le i-1,w_j=2），情况类似，方案数就是 suf_{i+1}。

时间复杂度 O(n^2)。