CF1784F Minimums or Medians

Alex_Wei · 2023-02-08 17:54:55 · 题解

先找充要条件。我们关注被删除的数。

首先，因为每次一定会删去剩余的连续两个数，所以 被删除的连续段长度一定是偶数，且对于两个不同的数 x, y，如果它们处在不同的连续段（以下均指被删除），那么不可能通过一次操作将它们删除。

其次，考虑从 1 开始的连续段，这段一定可以用操作一删除：考虑这段（以下称第一段）中最后一对被操作二删除的数，将该步操作替换为操作一，尽管当前被删除的数改变了，但因为接下来的操作二只涉及第二段及之后的数，所以不会对接下来的操作二产生影响（举例说明：用操作二删去 7, 8 时，之前删了 1, 2 还是 3, 4 没有影响）。

进一步地，操作一显然不会涉及除了第一段以外的所有段，故可得到重要结论：第一段中所有数被操作一删除，其它段中所有数被操作二删除。它不是一个条件，但使得接下来的推理更加自然。

因为在第 i 次操作时，较大的中位数一定是 n + i（易证），所以 不会删去大于 \boldsymbol {n + k} 的数。

结束了吗？非也。

因为操作二每次必然删去一个大于 n 的数，所以考虑一个不在第一段且不大于 n 的数 q，再考虑和它一起被删除的数 r。因为每次删去连续两个数且 q 不在第一段，所以当前 q + 1\sim r - 1 一定被操作二删光了。又因为每次操作二至多删去一个不大于 n 的数，所以这次操作二的编号一定不小于 n - q + 1。再结合第 i 次操作时较大中位数为 n + i，可知 r\geq n + (n - q + 1)。

因此，考虑不在第一段的最小的被删去的数 \boldsymbol {q}，则 \boldsymbol {q\sim 2n + 1 - q} 全部被删除。

结束了吗？好像结束了。

考虑任意满足上述三个加粗条件的集合，我们总可以构造出一组符合要求的方案：考虑所有连续段的右半部分，当中位数为这些数时，执行操作二，否则执行操作一。

接下来考虑计数，这部分是容易的。

首先，设 f(n, m) 表示从 n 个数中选出 2m 个数的方案数，其中所有选出的数形成的连续段长度为偶数。这相当于从 n - m 个数中选 m 个数，再将选出的数扩充成长度为 2 的连续段，故 f(n, m) = \binom {n - m} m。

枚举第一段长度 2p。

• 当 2p < n 时，再枚举第二段在 n 左侧的长度 c，则 c 不应超过 k - p（操作次数限制）和 n - 2p - 1（不能覆盖 2p + 1），有

  \begin{aligned} & \sum_{p = 0} ^ k[2p < n]\sum_{c = 0} ^ {\min(k - p, n - 2p - 1)} f(k - c, k - p - c) \\ & \sum_{p = 0} ^ k\sum_{c = 0} ^ {\min(k - p, n - 2p - 1)} \binom {p} {k - p - c} \end{aligned}

• 当 2p \geq n 时，剩余长度为 n + k - 2p - 1，剩余操作次数为 k - p，故有

  \sum_{p = 0} ^ {k} [2p\geq n]\binom {n - p - 1} {k - p}

时间复杂度 \mathcal{O}(n)。代码。