P10032 题解（2023 激励计划评分 8）

· · 题解

我们首先分析一下题目给出的操作。

对于某个元素 a_i，如果序列 a 中存在另一个元素 a_p 满足 a_i=a_p，那么显然，去掉 a_i 后的序列 a 的 \operatorname{mex} 和原本的序列 a 的 \operatorname{mex} 相等，所以操作后，a_i 会变成原本的序列 a 的 \operatorname{mex}。

同时，对于某个元素 a_j，若其满足 a_j 大于原本的序列 a 的 \operatorname{mex}，那么显然，是否去掉 a_j 对序列 a 的 \operatorname{mex} 没有影响，所以操作后，a_j 也会变成原本的序列 a 的 \operatorname{mex}。

我们再来考虑，对于某个元素 a_k，若其满足：

那么，去掉 a_k 之后，序列 a 的 \operatorname{mex} 就会变成 a_k，所以操作前后，a_k 的值不变。

于是我们明白了操作前后序列 a 的变化。可以用桶维护，做到以 \mathcal O(n) 的复杂度进行一次操作，那么对于 m=1 的情况，我们直接模拟即可。

我们继续分析。

我们先进行第一次操作，把所有满足序列 a 中存在另一个元素与其相等或其大于序列 a 的 \operatorname{mex} 的元素的值都修改为序列 a 的 \operatorname{mex}。

然后我们再进行第二次操作，内容和第一次操作相同。

于是容易证明，此时的序列 a 除最大值外，剩余的元素都满足不存在另一个元素 a_p 与其相等，而且最大值要么等于序列 a 的 \operatorname{mex} 的值加一，要么等于序列 a 的 \operatorname{mex} 的值减一。

我们设序列 a 中的最大值为 x。根据我们之前分析的内容，若序列 a 中只有一个元素的值为 x，则 x 的值不会再改变；若序列 a 中有多个元素的值为 x，我们分两类讨论：

可以发现，若序列 a 中有多个元素的值为 x，则进行多次操作时，x 的值在一直循环，不断加一、减一，每两次操作的效果可以抵消，于是可以得到：

那我们直接根据此模拟即可。

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+5;
int n,m,a[N],cnt[N];
void work(){
    int res=0;
    for(int i=0;i<=n;i++) cnt[i]=0;
    for(int i=1;i<=n;i++) if(a[i]<=n) cnt[a[i]]++;
    for(int i=n;i>=0;i--) if(cnt[i]==0) res=i;
    for(int i=1;i<=n;i++) if(a[i]>res||cnt[a[i]]>1) a[i]=res;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    work();
    if(m!=1){
        work();
        if(m%2==1) work();
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<(i==n?'\n':' ');
}
signed main(){
    ios::sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}