$\quad $ 说一个随机数据很快的方法。
$\quad $ 考虑优化 \(O(Tn ^2)\) 的暴力，首先枚举删数的位置，然后求出此时的最小序列。
$\quad $ 我们发现，当此时枚举的序列已经大于答案序列了，再去枚举该位置就毫无意义了，直接停止枚举即可，这样就会有70分。
$\quad $ 那么还可以怎么优化呢？
$\quad $ 注意到当原序列某一段全是0的时候，我们去删除这其中的各个元素所求出的答案是一致的，那么就可以利用并查集，在枚举过一个0之后直接将其后连续的0跳过。
$\quad $ 题库数据太水了，这样直接就是800ms，已经比大部分 \(O(Tn)\) 的做法快了（也可能是常数问题）。但还是可以卡掉，只要让原序列前一半的数确定，后一半0和非零交替即可。
$\quad $ 这样这个做法就直接退化成 \(O(Tn ^2)\) 了，甚至不用多测。
在这放个码吧
#define yhl 0
#include<bits/stdc++.h>
const int N=2e5+10;
#define int long long
int t,n,a[N],fa[N];
bool vis[N];
inline int read(){
int ans=yhl;char ch=getchar_unlocked();
while(ch<'0'||ch>'9')ch=getchar_unlocked();
while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar_unlocked();
return ans;
}
void print(int x){
(x>9)&&(print(x/10),yhl);
putchar_unlocked(x%10|48);
}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct string{
int a[N],siz;
}ans;
signed main(){
freopen("repeat.in","r",stdin);
freopen("repeat.out","w",stdout);
t=read();
while(t--){
n=read();
ans.siz=yhl;memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)ans.a[++ans.siz]=n*n;
for(int i=1;i<=n;i++)a[i]=read(),vis[a[i]]=(bool)a[i],fa[i]=i;
for(int i=1;i<n;i++)(!a[i])&&(!a[i+1])&&(fa[i]=i+1);
for(int i=1;i<=n;){
int top=1;string op;op.siz=yhl;
vis[a[i]]=yhl;bool flag=1,ft=yhl;
for(int j=1;j<=n&&flag;j++){
if(i!=j){
if(!a[j]){
while(vis[top])top++;
op.a[++op.siz]=top;
top++;
}else op.a[++op.siz]=a[j];
if(op.a[op.siz]<ans.a[op.siz])ft=1;
if(!(ft)&&op.a[op.siz]>ans.a[op.siz])flag=yhl;
}
}
vis[a[i]]=1;
if(flag)ans=op;
i=find(i)+1;
}
for(int i=1;i<=ans.siz;i++)print(ans.a[i]),putchar_unlocked(' ');
putchar_unlocked('\n');
}
return yhl;
}
$\quad $ 自己封了个string，其实没什么必要。
标签：定重,ch,yhl,int,vis,枚举,quad From： https://www.cnblogs.com/0shadow0/p/18439329