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

AllenJYL · 2025-11-29 15:50:40 · 题解

特判 m=1。先考虑正难则反，把会没掉的方案数算出来。

对 a 从大到小排序。考虑枚举一个 i 满足 w_i=2，此时任何 j<i,w_j=2 以及 2a_k>a_i,w_k=1 的糖果 j,k 都会被选中。注意根据定义，i 不会被选中。那么，没掉的方案有两种可能：

• 所有 w_k=1 的糖果 k 都满足 2a_k>a_i，他们都被选中。所有选中的糖果（包括 w 值为 2）的 w 之和恰为 m-1。
• 存在两个被选中的糖果 l,o 使得 w_l=w_o=1，l<o，2a_l>a_i，2a_o\le a_i 且所有 k>o,w_k=1 的糖果 k 都没被选中，所有 k\le l,w_k=1 的糖果 k 都被选中。所有选中的糖果（包括 w 值为 2）的 w 之和恰为 m。

对于第一种情况，枚举 w_i=2 的 i，以及 a_j 最小（也就是 j 最大）的 w_j=1 的糖果 j。这个 j 需要满足：

• 对于所有 k>j，w_k=2。

此时，这个方案能产生贡献当且仅当 a_j<a_i。把上面的东西判完之后对这样的方案计数：

• 我们要在前 \max(i,j) 个位置中去除掉 i,j 这两个已经知道 w 值的位置，剩下的 \max(i,j)-2 个位置中填入合适数量的 1 和 2，使得下列两个值：

  • 满足 l<i,w_l=2 的 l 的数量乘 2；
  • 满足 l<j,w_l=1 的 l 的数量。

  加起来正好等于 m-2（这里为什么不是 m-1 是因为 j 也会被选中，要去掉它）。同时，我们还要求对于 j<l<i，w_l=2。若 j>i 则无限制。

  这样的方案数记作 d_{i,j}，具体求法见下文。

• 剩下的位置填 2，方案数为 1。

对于第二种情况，枚举 w_i=2 的 i，以及上文提到的 l,o。此时需要满足：

• 对于所有 l<k<o，w_k=2。

此时，这个方案能产生贡献当且仅当 a_l+a_o<a_i。把上面的东西判完之后对这样的方案计数：

• 我们要在前 \max(i,l) 个位置中去除掉 i,l 这两个已经知道 w 值的位置，剩下的 \max(i,l)-2 个位置中填入合适数量的 1 和 2。。。等等？这和第一种情况里的如出一辙，那我们就知道这个值为 d_{i,l}。
• 我们要在后 o-1 个位置中任意选，所以这个方案数是 2^{n-o}；
• 我们要在 \max(i,l)<k<o 的 k 中填 2，o 中填 1。方案数为 1。

现在，如果我们知道怎么求 d_{i,j}，那就可以 O(n^3)。在求 d 之前，我们先把第二种情况优化一下，使得除去求 d，剩下的复杂度为 O(n^2)。

我们发现，第二种情况的 o 可以扔到外面去，具体地，固定 i，随着 l 的增加，满足条件的 o 一定是个后缀，而这个后缀的边界会越来越向左，直到边界撞上 \max(i,l) 为止。撞上之后，任何 o>l 的 o 都将满足条件。因此我们拿个指针维护这个边界，随着边界向左扩张动态维护当前的总方案数就可以了。

问题变为了求 d_{i,j}。

• 对于 i>j，注意到此时 1\sim i 中 w 值为 1 的位置数是固定的，d_{i,j} 就是一个组合数；

• 对于 i<j，我们发现下面两个值的和：

  • 满足 l<i,w_l=2 的 l 的数量；
  • 满足 i<l<j,w_l=1 的 l 的数量。

  是定值，此时 d_{i,j} 也是一个组合数。

至此我们完成了本题，时间复杂度 O(n^2)。