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

赛时花费 $3\text{h}+$ 通过大样例，自造数据 $1.07\text{s}$，希望别死。

设确定 $w$ 后，从大到小排序后的 $\frac{a_i}{w_i}$ 数组为 $b$，不妨设 $b_i$ 对应的就是 $a_i,w_i$。

观察一个不合法的情况，形如取了一个前缀到 $b_x$ 之后，还剩 $1$ 块钱，然后遇到几个 $w_z=2$ 取不到，然后再遇到一个 $w_y=1$ 刚好把 $1$ 块钱用完（可能不存在 $y$）。这里，如果 $a_x+a_y<a_z$，那么把 $x,y$ 换为 $z$ 就是更优的，这时候就不合法了。

然后一个自然的想法是，枚举 $x,y,z$，算出方案数 $\text{calc}(x,y,z)$，然后省掉其中一维就可以做到 $\mathcal{O}(n^2)$。

这个 $\text{calc}(x,y,z)$ 实在是非常难算！

首先可以钦定，$z$ 为从左到右第一个满足 $\text{calc}(x,y,z)\neq 0$ 的 $z$，以方便去重。

需要计算的方案数可以分成三部分：$[1,z-1],[z+1,y-1],[y+1,n]$，显然 $w_z=2,w_x=w_y=1$。

先考虑 $[1,z-1]$ 部分，我们需要求出为 $[1,z-1]$ 所有数确定 $w$ 的方案数，使得按照原策略取时，恰好在 $z$ 所在的位置剩下 $1$ 块钱。由于 $x$ 是除了 $y$ 之外最后一个被取到的 $w=1$，$x$ 到 $z$ 部分的 $w$ 必须为 $2$。

$[1,z-1]$ 中的点实际上有两类：一种是 $w=2$ 时仍然在 $z$ 前面的点，这样的点形成一个前缀，另一种是 $w=2$ 时跳出 $z$ 的点。

大概长这样（有点丑见谅），对于第一种点，其对 $m$ 的减量为 $1$ 或 $2$，对于第二种点，其对 $m$ 的减量为 $0$ 或 $1$。设对于 $[1,z]$ 而言，这两种点的数量分别为 $c_{1,z},c_{2,z}$。

把 $a_i,\frac{a_i}2$ 放一起排个序，统计前缀有多少个 $a_i$ 多少个 $\frac{a_i}2$ 即可得到 $c_{1,i},c_{2,i}$。

下面一步非常重要：不妨设 $m$ 已经减掉了 $c_{1,z}$。 这样两种点就本质上相同了，只需要再选任意 $m-c_{1,z}-2$ 个点即可（忽略了 $x$ 的贡献，所以是 $-2$），注意 $[x+1,z-1]$ 范围内的点只能选择贡献为 $0$，所以实际上是从 $c_{1,x-1}+c_{2,x-1}-1$（忽略 $z$）个点中选，于是方案数 $\binom{c_{1,x-1}+c_{2,x-1}-1}{m-c_{1,z}-2}$。

接下来考虑 $[z+1,y-1]$ 部分，这个部分只有 $w=2$，要求所有在其中的点都 $w=2$ 即可，没有贡献。

最后是 $[y+1,n]$ 部分，这个部分包含了跳过来的 $w=2$，这些点没有贡献，以及 $w=1,2$ 时都会在这个部分的点，这样的点可以任选 $w=1$ 或 $w=2$，每个点有 $2$ 的贡献，这样的点的数量可以通过与前文类似的方式求出，设为 $d_y$，则方案数 $2^{d_y}$。

于是得到 $\text{calc}$ 的表达式。

直接枚举满足 $a_x+a_y<a_z,a_x<\frac {a_z}2<a_y$ 的 $x,y,z$ 可以做到 $\mathcal{O}(n^3)$。注意处理相等的情况。

注意到对于一对 $x,z$，合法的 $y$ 形如一个后缀，同时随着 $a_x$ 的增加，$y$ 的变化也是单调的，于是可以在枚举 $x,z$ 时用一个指针维护 $y$ 的边界，再预处理出 $2^{d_y}$ 的后缀和，可以做到 $\mathcal{O}(n^2)$。