标签：2t 选出 训练 删除 记录 sum len 2023 操作

训练记录

9 月没做题。

---

不能摆了，再摆就完蛋了。

CF1784F Minimums or Medians

很厉害的题。

我们考虑找充要条件：

1. 注意到所有被删除的连续段长度都是偶数。并且不同的连续段之间，都是被分开删除的。

   注意到只有从 \(1\) 开始的连续段才可能用操作 1 删除，于是其它被删的数都是通过操作 2 删除的。

2. 注意到第 \(i\) 次若为操作 2，则删除的较大数为 \(i+n\)，所以，被删除的数都必须 \(\le n+k\)。

3. 注意到若删除了数 \(t\le n\) 不在第一段，则 \([t,2n-t+1]\) 的数都必须被删除。

上述 3 个必要条件是充分的，因为考虑我可以通过构造，每次能用操作 2 就用操作 2，否则就用操作 1，不难发现一定是合法的。

设函数 \(f(n, m)\) 表示长度为 \(n\) 的段中，选出 \(2m\) 个数，并要求选出的数形成长度为偶数的连续段。考虑捆绑法，我们没选出一个数就要求必须选它后面的那个数，于是这样就只有 \(n-m\) 个物品，从中选出 \(m\) 个，所以是 \(\binom{n-m}{m}\)。

考虑如何计数。首先，我们枚举从 1 开始的连续段需要操作的次数 \(t\)，因为涉及到条件 3，所以我们需要根据是否覆盖超过一半来分类讨论：

1. \(2t < n\)，于是再枚举在 \(n\) 之前被删掉的连续段长度 \(c\)，于是得到：

\[\sum_{t=1}^{\min\{k, \lfloor \frac{n-1}{2} \rfloor\}} \sum_{c=0}^{\min\{k - len, n - 2k - 1\}}f(k-c,k-t-c) \]

注意到 \(len\) 增加时，组合数的变化可以 \(O(1)\) 维护，类似莫队移动指针，加入或删除组合数。

2. \(2t \ge n\)，那么剩下的就可以随便操作，于是对答案的贡献为：

\[\sum_{len = \lceil\frac{n}{2}\rceil}^{k} f(n + k-2t-1, k - t) \]

记录。

标签：2t,选出,训练,删除,记录,sum,len,2023,操作
From： https://www.cnblogs.com/zhaohaikun/p/17700129.html