Codeforces Global Round 9 D. Replace by MEX(構造)⭐⭐⭐

傳送門

又是構造瞎搞題，太難啦。

是這樣的，首先考慮一個點：

就是每次的mex是可以算出來的，然後這時候你可以任選你可以任選一個點把值設定為mex,如果你之後不再動這個點，那麼再也不會出現這個mex的值了。那是不是就比較清晰了。

我們不妨構造一個 a [ i ] = i − 1 a[i]=i-1 a[i]=i−1的序列。

如果mex的值為n,就任選一個值不符合的待更新的位置，設成n,那麼下次的mex肯定不為n,因為mex不會出現a中目前已有的值。如果mex值不為n,就放到對應位置上即可。

這樣最多經過不超過2*n次替換就可以構造出序列了~

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define MAXN 1005
#define ll long long
ll a[MAXN];
int main()
{
    int  t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        vector<int>ans;
        for(int i=1;i<=n;i++) {
            scanf("%lld", a + i);
        }
        for(int i=1;i<=2*n;i++)
        {
            int now=0;
            vector<int>cnt;
            for(int j=1;j<=n;j++)
                cnt.push_back(a[j]);
            sort(cnt.begin(),cnt.end());
            for(int j=0;j<cnt.size();j++)
            {
                if(cnt[j]==now)now++;
            }
            if(now==n)
            {
                for(int j=1;j<=n;j++)
                {
                    if(a[j]!=j-1){
                        ans.push_back(j);
                        a[j]=n;
                        break;
                    }
                    if(j==n)i=2*n;
                }
            }
            else
            {
                if(a[now+1]!=now)
                    ans.push_back(now+1);
                a[now+1]=now;
            }
        }
        cout<<ans.size()<<endl;
        for(auto it:ans)
            printf("%d ",it);
        printf("\n");
    }
}