P10032题解

b1tset · 2024-01-01 12:25:52 · 题解

显然，打一份代码模拟题意即可找到规律：任意数列进行两次操作后就会陷入循环。

Part 1.证明：

分类讨论，讨论数列中 0 的个数。

• 若数列中没有 0：一次操作后就会全变为 0，再一次操作就会全变为 1，进入循环。
• 若数列中只有一个 0 ： 0 一直不变，剩下数字等同于一个没有 0 的数列，进入循环。
• 若序列中有大于等于二个 0：第一次操作全变得非 0，再进行一次操作就全变成 0，进入循环。

综上，任意数列进行两次操作后就会陷入循环

所以我们只需要提前进行两次操作即可。若要求的操作数为奇数，则再进行一次操作。注意特判要求只做一次操作的情况。

549ms。

Part 2.高效地进行操作

1. 我们先把每一个小于 n 的数统计出来。我们知道，任意一个长度为 l 的数列的 mex 值一定在 0 到 l 之间，所以统计小于 n 的数的个数即可。
2. 用 O(n) 的复杂度求出数列的 \operatorname{mex} 值。
3. 这时开始遍历数组，分三种情况。

• 若该数已经大于原数列的 \operatorname{mex} 值，则数列除去该数后的 \operatorname{mex} 值依然是 原数列的 \operatorname{mex} 值。
• 若该数小于原数列的 \operatorname{mex} 值且在数列中只出现了一次，则数列除去该数后的 \operatorname{mex} 值是该数的值。
• 若该数小于原数列的 \operatorname{mex} 值且在数列中出现了多次，则数列除去该数后的 \operatorname{mex} 值依然是原数列的 \operatorname{mex} 值。

我们就做到了在 O(n) 的时间复杂度进行一次操作！

code

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

int n, m, mnx;
int a[1000005], vis[1000005];

void mex() //题目里的一次操作
{
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++) //记录每个数的出现次数。
        if (a[i] <= n) //记录从0~n的数即可，无需记到m
            vis[a[i]]++;
    for (int i = 0; i <= n; i++) //最小出现的自然数
        if (!vis[i])
        {
            mnx = i;
            break ;
        }

    for (int i = 1; i <= n; i++)
    {
        int x = a[i];
        if (x > mnx) //比最小出现的自然数大
            a[i] = mnx;
        else if (vis[x] == 1) //只出现一次，且比最小出现的自然数小
            a[i] = x;
        else
            a[i] = mnx;
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(vis, 0, sizeof vis); //多测要清空。
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        if (m == 1) //特判
            mex();
        else
        {
            mex();
            mex(); //先进行两次操作
            if (m & 1) //如果操作数为奇数则再操作一次
                mex();
        }

        for (int i = 1; i <= n; i++) //输出
            printf("%d ", a[i]);
        puts("");
    }
    return 0;
}

/*
不知不觉2024年了..
时间过得很快啊..
祝大家新年快乐！

Fighting & 做最好的自己！

iYW :)
*/