欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

codeforces 1375D 模拟+思维

程序员文章站 2022-06-23 08:38:43
1375D 1900的题题意:给你一个n,然后是一个数组,其中的值为0~n,定义mex为数组中0~n不存在的最小的那个,操作为可以将第i个数字为mex,使得这个数组为不递减的数组,可以证明操作次数在2n次内一定能实现,问你操作次数是多少,并输出相对应的索引,操作次数不要求是最优的。思路:看到在2n次内一定能实现,并且不要求是最优的,可以想到我们一定可以把这个数组变为一个我们想变成的数组,例如1~n的递增,或者说是0~n-1的递增,通过模拟可以知道这两种情况在特定的条件下都是能够实现的。首先当mex=n...

1375D 1900的题
题意:给你一个n,然后是一个数组,其中的值为0~n,定义mex为数组中0~n不存在的最小的那个,操作为可以将第i个数字为mex,使得这个数组为不递减的数组,可以证明操作次数在2n次内一定能实现,问你操作次数是多少,并输出相对应的索引,操作次数不要求是最优的。
思路:看到在2
n次内一定能实现,并且不要求是最优的,可以想到我们一定可以把这个数组变为一个我们想变成的数组,例如1~n的递增,或者说是0~n-1的递增,通过模拟可以知道这两种情况在特定的条件下都是能够实现的。
首先当mex=n时,可以将a【n-1】=mex,同时n–。
当mex!=n是,a【mex】=mex。
可以知道这种操作在2*n次内一定能够实现。
代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define rep(i, a, n) for(int i = a; i <= n; i++)
#define per(i, a, n) for(int i = n; i >= a; i--)
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fopen freopen("file.in","r",stdin);freopen("file.out","w",stdout);
#define fclose fclose(stdin);fclose(stdout);
#define PI 3.14159265358979323846
const int inf = 1e9;
const ll onf = 1e18;
const int maxn = 1e5+10;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int a[1010];
int vis[1010], n;
int solve(){
    rep(i,0,n) vis[i]=0;
    rep(i,0,n-1) vis[a[i]]++;
    rep(i,0,n) if(vis[i]==0) return i;
    return 0;
}
inline void cf(){
    int t = read();
    while(t--){
        n = read();
        rep(i,0,n) vis[i] = 0;
        rep(i,0,n-1) a[i]=read();
        std::vector<int> v;
        while(n>0){
            int mex = solve();
            if(mex==n){
                v.push_back(n-1);
                a[n-1] = n;
                n--;
            }else {
                v.push_back(mex);
                a[mex] = mex;
            }
        }
        int op = v.size();
        printf("%d\n", op);
        rep(i,0,op-1) printf("%d ", v[i]+1);
        printf("\n");
    }
    return ;
}
signed main(){
    cf();
    return 0;
}

本文地址:https://blog.csdn.net/acm123456789ctf/article/details/107869816