传送门

【题目分析】

什么神仙题都拿来当T2。。。。。

首先还是列出比较明显的性质：

1.两个相同非零数之间的长度为奇数

2.一头一尾非零但不相等无解

3.一段区间如果已知数字互不相同，如果0的个数小于区间长度的一半，无解（即下去了上不来）

4.子树区间要么完全包含要么不相交，相交不包含无解

有以上几个性质就可以排除一些情况，然后是填数。

对于当前处理的区间[L,R]，对于区间中与a[L]相等的数，明显两点之间就是一颗子树，递归求解，然后删除这段区间。

最后剩下的就是0和未配对的数，在性质3的限制下随机填数即可。

然后对于所有0xy，直接填成yxy；同理，所有yx0填成yxy。

最后剩下的全部填当前子树的根节点就好了。

【代码~】

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n;
int a[MAXN];
int pre[MAXN],suf[MAXN],nxt[MAXN];
int app[MAXN],now=1;
int last[MAXN];
int Read(){
int i=0,f=1;
char c=getchar();
for(;(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void del(int l,int r){
pre[suf[r]]=pre[l];
suf[pre[l]]=suf[r];
}
int gen(){
while(last[now])
++now;
if(now>n){puts("no");exit(0);}
last[now]=-1;
return now;
}
void solve(int l,int r){
if((r-l)%2==1){puts("no");exit(0);}
for(int i=l;i<=r;i=suf[i]){
while(nxt[i]){
if(nxt[i]>r){puts("no");exit(0);}
solve(suf[i],pre[nxt[i]]);
del(suf[i],nxt[i]);
nxt[i]=nxt[nxt[i]];
}
}
int sum=0,cnt=0,rt=a[pre[l]];
for(int i=l;i<=r;i=suf[i])
++sum,cnt+=a[i]>0;
sum=(sum+1)/2;
if(cnt>sum){puts("no");exit(0);}
for(int i=suf[l];i<=r;i=suf[i])
if(!a[i]&&cnt<sum)
a[i]=gen(),++cnt;
if(sum==1&&!cnt)
a[l]=gen();
for(int i=l;suf[i]<=r;i=suf[i]){
while(i>l&&suf[i]<=r&&!a[pre[i]]&&a[i]&&a[suf[i]])
a[pre[i]]=a[suf[i]],del(i,suf[i]),i=pre[pre[i]];
while(i>=l&&suf[suf[i]]<=r&&a[i]&&!a[suf[suf[i]]]&&a[suf[i]])
a[suf[suf[i]]]=a[i],del(suf[i],suf[suf[i]]),i=pre[i];
}
for(int i=l;i<=r;i=suf[i])
if(!a[i])
a[i]=rt;
}
int main(){
n=Read();
for(int i=1;i<=n*2-1;++i)
a[i]=Read();
if(a[1]&&a[n*2-1]&&a[1]!=a[n*2-1]){puts("no");return 0;}
int tmp=a[1]|a[n*2-1];
a[1]=a[n*2-1]=tmp;
for(int i=0;i<=n*2-1;++i)
pre[i]=i-1,suf[i]=i+1;
for(int i=n*2-1;i;--i){
if(a[i]){
nxt[i]=last[a[i]];
last[a[i]]=i;
}
}
solve(1,n*2-1);
puts("yes");
for(int i=1;i<=n*2-1;++i)
cout<<a[i]<<' ';
}

最后

以上就是光亮铃铛为你收集整理的CF1053E Euler tour（构造）传送门【题目分析】【代码~】的全部内容，希望文章能够帮你解决CF1053E Euler tour（构造）传送门【题目分析】【代码~】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。