题解

题意简述

给定 $n, m, k$，满足 $m \cdot k < n$。定义 $f(b)$ 为对序列 $b$ 进行至多 $m$ 次“删除长为 $k$ 的连续子数组”操作后，可能得到的序列的 $\operatorname{mex}$ 的最小值。要求构造一个长为 $n$ 的序列 $a$（元素在 $[0,10^9]$），使 $f(a)$ 最大。

---

思路分析

1. 基本观察

• 删除操作不会增加 $\operatorname{mex}$，所以最多 $m$ 次等价于恰好 $m$ 次（可以补空操作）。
• 最终序列长度 $L = n - m \cdot k$。
• 显然 $\operatorname{mex} \le L$，因此：$$f(a) \le n - m \cdot k$$

---

2. 考虑每个数字的出现次数

若我们想让 $\operatorname{mex} \ge x$，那么 $0,1,\dots,x-1$ 必须都在最终序列中出现。
每次删除最多能去掉每个数字的一个出现（因为删除的是连续段，但一个数字可能在不同位置出现多次）。
因此，若某个数字在原始序列中出现 $cnt$ 次，则它在最终序列中至少还有 $cnt - m$ 次（因为一次删除至多删掉一个该数字）。

为了让 $0 \sim x-1$ 在最终序列中至少出现一次，每个这样的数字必须满足：

$$cnt \ge m + 1$$

否则可能被 $m$ 次删除全部删光。

因此，在原始序列中，$0 \sim x-1$ 必须各出现至少 $m+1$ 次。
总长度要求：

$$n \ge (m+1) \cdot x \quad \Rightarrow \quad x \le \frac{n}{m+1} $$

所以：

$$f(a) \le \left\lfloor \frac{n}{m+1} \right\rfloor$$

---

3. 综合上界

由以上两点：

$$f(a) \le \min\left(n - m \cdot k,\ \left\lfloor \frac{n}{m+1} \right\rfloor\right) $$

我们声称这个上界可达，即：

$$f_{\max} = \min\left(n - m \cdot k,\ \left\lfloor \frac{n}{m+1} \right\rfloor\right) $$

---

4. 构造证明

分两种情况：

情况 1：$n - m \cdot k < \frac{n}{m+1}$
即 $n - m \cdot k < \frac{n}{m+1}$。整理得：

$$n - m \cdot k < \frac{n}{m+1} \quad\Rightarrow\quad n - \frac{n}{m+1} < m \cdot k $$$$\frac{(m+1)n - n}{m+1} = \frac{m n}{m+1} < m \cdot k \quad\Rightarrow\quad \frac{n}{m+1} < k $$

此时 $n - m \cdot k < k$，即最终长度小于 $k$。

构造：$a_i = i \bmod k$（即 $0,1,\dots,k-1$ 循环）。
由于 $k > n - m \cdot k$，最终剩余的部分必然严格递增 $0,1,2,\dots$（因为循环周期 $k$ 且 $k$ 大于剩余长度）。
无论删哪 $m$ 个长为 $k$ 的段，剩余部分形如连续的一串 $i \bmod k$ 且长度为 $n - m \cdot k$，其 $\operatorname{mex}$ 就是该长度（即 $n - m \cdot k$）。
因此 $f(a) = n - m \cdot k$，达到上界中较小的那个。

---

情况 2：否则，即 $\frac{n}{m+1} \le n - m \cdot k$，但注意 $\lfloor n/(m+1) \rfloor$ 可能小于等于 $k$。此时最大 $\operatorname{mex}$ 由 $\lfloor n/(m+1) \rfloor$ 决定。

构造：设 $x = \lfloor n/(m+1) \rfloor$。取：

$$a_i = i \bmod x$$

这样 $0 \sim x-1$ 每个数出现次数：

• 如果 $n = q \cdot x + r$，则前 $r$ 个数出现 $q+1$ 次，其余 $x-r$ 个数出现 $q$ 次。
• 因为 $q = \lfloor n/x \rfloor \ge m+1$（根据 $x \le n/(m+1)$ 得 $n/x \ge m+1$），所以每个 $0\sim x-1$ 至少出现 $m+1$ 次（前 $r$ 个出现更多）。

此外，相同数字的间隔至少为 $x \ge k$（因为 $x = \lfloor n/(m+1) \rfloor$ 且 $n/(m+1) \ge k$ 在情况 2 中成立）。
因此，每次删除一个长为 $k$ 的段最多只能删掉每个数字的一个副本。经过 $m$ 次删除，每个 $0 \sim x-1$ 至少剩余一次，所以最终 $\operatorname{mex} \ge x$。

又因为最终长度 $n - m \cdot k \ge x$（情况 2 的前提），所以 $\operatorname{mex} = x$ 可达。因此 $f(a) = x = \lfloor n/(m+1) \rfloor$。

---

算法实现

按上述构造，一行判断：

• 若 $n < (m+1)k$，取模 $k$；
• 否则取模 $\lfloor n/(m+1) \rfloor$。

时间复杂度 $O(n)$ 打印。

---

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        int mod = (n < (m + 1) * k) ? k : n / (m + 1);
        for (int i = 0; i < n; ++i) {
            cout << i % mod << " \n"[i == n - 1];
        }
    }
    return 0;
}