CF 1863 C

C. MEX Repetition

通过观察样例，直接猜结论可知，例如第二个样例\([0, 1, 3]\)后面其实有一个隐藏数字（2），所以完整的排列为\([0, 1, 3, 2]\)。然后每一次操作都是把最后的一位数字移到整个排列的最前面，并把最后一位隐藏，所以直接取模就能求出最后的排列。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 1e5 + 10;
int t;
int n, k;
int a[N];
bool v[N];
signed main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        memset(v, 0, sizeof(bool) * (n + 1));
        for(int i = 0;i < n;i++)
        {
            cin >> a[i];
            v[a[i]] = 1;
        }
        for(int i = 0;i <= n;i++)
        {
            if(!v[i])
            {
                a[n] = i;
                break;
            }
        }
        int cnt = 0;
        for(int i = (-k % (n + 1) + (n + 1)) % (n + 1);cnt < n;cnt++, i = (i + 1) % (n + 1))
        {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}