题解：CF1863C MEX Repetition

liuli688 · 2023-12-11 17:29:48 · 题解

题意：

对于序列里的每一个数 a_i，将它换成 MEX(a_1,a_2,\dots,a_n)，MEX 指不在数组中的最小非负整数。求操作 k 次后的序列。

思路：

没思路？手玩样例！

把输入输出样例暴力一下。

注：分隔线是用来分隔题面要求计算的情况和不需计算的情况的。注意前面标.的情况。

#1:

• k = 0$：$[1] k = 1$：$[0]
• k = 2$：$[1]

#2:

• k = 0$：$[0,1,3] k = 1$：$[2,0,1] k = 2$：$[3,2,0] k = 3$：$[1,3,2]
• k = 4$：$[0,1,3]

#3:

• k = 0$：$[0,2] k = 1$：$[1,0] k = 2$：$[2,1] k = 3$：$[0,2]

#4:

• k = 0$：$[1,2,3,4,5] k = 1$：$[0,1,2,3,4] k = 2$：$[5,0,1,2,3] k = 3$：$[4,5,0,1,2] k = 4$：$[3,4,5,0,1] k = 5$：$[2,3,4,5,0]
• k = 6$：$[1,2,3,4,5]

#5：

• k = 0$：$[5,3,0,4,2,1,6,9,10,8] k = 1$：$[7,5,3,0,4,2,1,6,9,10]

  注：10 + 1 = 11，由于 100 \bmod 11 = 1，所以在这里分隔。

  k = 2$：$[8,7,5,3,0,4,2,1,6,9] k = 3$：$[10,8,7,5,3,0,4,2,1,6] k = 4$：$[9,10,8,7,5,3,0,4,2,1] k = 5$：$[6,9,10,8,7,5,3,0,4,2] k = 6$：$[1,6,9,10,8,7,5,3,0,4] k = 7$：$[2,1,6,9,10,8,7,5,3,0] k = 8$：$[4,2,1,6,9,10,8,7,5,3] k = 9$：$[0,4,2,1,6,9,10,8,7,5] k = 10$：$[3,0,4,2,1,6,9,10,8,7]
• k = 11$：$[5,3,0,4,2,1,6,9,10,8]

可知，MEX 有一个循环，周期为 n + 1。所以实际计算的 k 是 k \bmod (n + 1)。设它为 len。

找规律：

• 若 len = 1，则先输出 MEX，再输出 a_1,a_2,\dots,a_{n - 1}。
• 若 len = n，则先输出 a_2,a_3,\dots,a_n，再输出 MEX。
• 否则先输出 a_{n - len + 2},a_{n - len + 3},\dots,a_n，再输出 MEX，最后输出 a_1,a_2,\dots,a_{n - len}。

找到规律后，代码就很容易写了。

代码：

#include <bits/stdc++.h>
using namespace std;
int t,n,m,k,len,i,a[100000];
bool bk[100001];//bk是在求 MEX 时用的标记数组
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//防 T 技巧（实际上也不一定会用）
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        memset(bk,false,sizeof(bk));//把标记数组重置
        for(i = 0;i < n;i++)
        {
            cin >> a[i];
            bk[a[i]] = true;//记录一下是否出现
        }
        for(i = 0;i <= n;i++)
            if(!bk[i])
            {
                m = i;//m 就是 MEX 的结果
                break;//防 T
            }
        len = k % (n + 1);//len 同上
        if(len == 1)//特判 len = 1
        {
            cout << m << ' ';
            for(i = 0;i < n - 1;i++)
                cout << a[i] << ' ';
            cout << '\n';
        }
        else if(len == n)//特判 len = n
        {
            for(i = 1;i < n;i++)
                cout << a[i] << ' ';
            cout << m << '\n';
        }
        else//按上面处理
        {
            for(i = n - len + 1;i < n;i++)//输出前半部分
                cout << a[i] << ' ';
            cout << m << ' ';
            for(i = 0;i < n - len;i++)//输出后半部分
                cout << a[i] << ' ';
            cout << '\n';
        }
    }
    return 0;
}