-
P14636 NOIP2025 清仓甩卖 / sale
考虑这个策略为啥会爆。发现当选取了一段价值和为 m-1 的前缀之后，就只能取接下来的一个 1 了。但是如果这个前缀后面的 2 可以代替这个 1，以及前缀中价值最小的 1，那么就爆了。考虑刻画这个性质。假设 \(a_k\) 代替了 \(a_i\) 和 \(a_j\)。那么我们枚举 \(i\) 和 \(k\)。将所有物品归类为以下几类：
如果 \(w\) 为 \(1\) 的时候在 \(i\) 前面，\(w\) 为 \(2\) 的时候仍然在 \(k\) 前面，那么称之为 A 类。对前缀可能造成 +1/+2 的贡献。
如果 \(w\) 为 \(1\) 的时候在 \(i\) 前面，\(w\) 为 \(2\) 的时候在 \(k\) 后面，那么称之为 B 类。对前缀可能造成 +0/+1 的贡献。
如果 \(w\) 为 \(1\) 的时候就在 \(j\) 的后面，那么只要把方案数乘上 \(2\) 即可。
我们希望对 A 类和 B 类物品进行选择，使得和为 \(m-2\)。容易发现只要知道 A 类和 B 类物品的个数，贡献就是一个组合数。而固定了 \(i\) 和 \(k\)，知道 A 类和 B 类物品的个数是容易的，可以 \(O(1)\) 求出。现在只要关心：对于所有可能的 \(j\)，贡献系数的和是多少。发现将 \(a_i\) 从大到小排序后可能的 \(j\) 是一段后缀，因此只要知道了有多少个可能的 \(j\)，贡献系数的和就是某个 \(2\) 的次幂减去 \(1\)。求多少个可能的 \(j\) 也是容易的，直接双指针一下即可。发现还有一种情况是后面全是 \(w=2\)，没有选择任何一个 \(j\)。处理这种情况是容易的，此时贡献系数的和变成了某个 \(2\) 的次幂。总复杂度 \(O(n^2)\)。
