题解 CF1863C MEX Repetition

CF1863C MEX Repetition

简要题意

给定一个 $n$ 个元素的序列 $a$，其中的元素由小于等于 $n$ 的自然数构成且元素之间两两不同。现在定义一种操作，该操作会将第 $i$ 个位置的元素 $a_i$ 替换为该序列中当前没有的最小自然 数。每一轮操作都会从 $1$ 位置一直替换到 $n$。给定整数 $n,k$ 和序列 $a$，其中 $k$ 表示要进行 $k$ 轮操作，要求输出操作后的序列。

策略分析

题目中其实有一个诈骗条件。因为序列中的 $n$ 个元素包含小于等于 $n$ 的自然数且两两相同，所以我们可以发现，如果把原序列增加 $1$ 个元素，那么这个序列就变成了 $0 \sim n$ 的一个排列。而我们要替换用的那个数其实就是原序列中没有出现的那个数。我们发现，每当我们替换了一个数字，那么我们必然要用替换下来的这个数字去替换下一个数字，因为被替换下来的这个数字变成了当前序列中缺少的那个数。我们将最开始序列中缺少的那个数放在第 $n + 1$ 个位置。然后我们就可以显然地发现，每次操作实质上就是用第 $i$ 个位置的元素去替换第 $i+1$ 个位置的元素，推广到递推形式就是：
$$
a_{(i+1) \operatorname{mod} (n+1)}= a_{i \operatorname{mod}(n+1)}
$$
现在我们就知道了替换的方法，但是如果我们按照这个递推式进行模拟显然是行不通的，所以我们需要对这个做法进行优化。我们发现，每一轮操作结束后，都相当于把这个序列滚动一次，我们以下面的输入为例：

5 5
1 2 3 4 5

我们把没有出现的元素放在第 $n+1$ 个位置，然后我们每次进行一轮操作并记下来：

1 2 3 4 5 0
0 1 2 3 4 5
5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2 
2 3 4 5 0 1
1 2 3 4 5 0

于是我们就发现了，这种操作具有循环节，每一轮循环次数等于 $n+1$。原序列的元素顺序也没有太大的改变，所以我们就可以先确认没有第一次操作前没有出现的那个元素的位置，不难发现这个元素的位置等于 $k \operatorname{mod} (n+1)$。那么我们就可以直接做了。

参考代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

namespace SHAWN {
    const int N = 1e5 + 7;
    int a[N];
    bool chk[N];
    int T, n, k;
    int work()
    {
        cin >> T;
        while (T--) {
            cin >> n >> k;
            for (int i = 1; i <= n; ++i) {
                cin >> a[i];    
                chk[a[i]] = true;
            }
            int fir;
            for (int i = 0; i <= n; ++i) {
            // 不想写二分了所以直接 O(n) 查
                if (!chk[i]) {
                    fir = i;
                    break;
                }
            }
            a[++n] = fir;
            int xh = k % n, cnt = n - 1;
            int idx = n - xh + 1;
            while (cnt--) {
                if (idx > n) { idx = 1; }
                cout << a[idx++] << ' ';
            }
            cout << '\n';
            memset(chk, 0, sizeof(chk));
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}