【CF1053E】Euler tour

题面

CF

洛谷

大概意思是你有一棵树，然而你并不知道这棵树是啥。给你一个确定了一些位置的欧拉序（就是\(ST\)表求\(LCA\)的那个序列），问你是否存在一个合法的序列，如果可以构造出一个。

题解

首先我们一定能够确定的是以下性质：

\(a_1=a_{2n-1}\)，因为首位肯定都是根节点
如果\(a_i=a_j\)，那么两个位置中间的数的个数一定是偶数个，即\(i,j\)同奇偶。因为子树内每条边都会给序列贡献两个点，所以贡献的点数一定是偶数。
两个两侧端点是同一节点的区间如果有交，那么它们一定是包含关系。如果有交证明一个一定在另外一个子树内，所以必定是包含关系。

接下来考虑怎么构造，假设我们当前要构造的是区间\([l,r]\)，首先这个区间要满足上面的性质。

然后从左往右扫一遍\([l,r]\)，如果发现\(a_i=a_l\)，证明\([lst,i]\)这段区间内是一棵子树，其中\(lst\)是\(a_i\)上一次出现的位置，那么可以递归处理这棵子树，处理完了之后可以直接删掉。

对于剩下的所有位置一定两两不成子树（如果成子树就会在前面被递归了），先统计一下总数和不同的节点数，看看空位置的数量够不够两两匹配，如果不够肯定不解。

首先空位置的数量一定要是确定的数字的两倍，那么首先从前往后填未出现过的数字把一部分空位置给填上。

然后如果连续三个位置形如\(0xy\)，那么第一可以把它填成\(yxy\)，如果连续三个位置形如\(xy0\)，那么可以变成\(xyx\)。注意这里因为所有数字都只会出现一次，所以这样子才是对的。

这样子处理完只有一个三元组\(xyx\)只需要保留一个\(x\)，于是这样子能够把所有\(0\)基本填满。

如果还有没有填满的位置，那么直接填上这段区间的根节点就行了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 1000100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

void Fail(){puts("no");exit(0);}

int n,m,a[MAX],pre[MAX],suf[MAX],vis[MAX],nxt[MAX];

void Del(int l,int r){suf[pre[l]]=suf[r];pre[suf[r]]=pre[l];}

int nw=1;

int get()

{

	while(vis[nw])++nw;

	if(nw>n)Fail();

	vis[nw]=-1;return nw;

}

void Solve(int l,int r)

{

	if((r-l)&1)Fail();

	for(int i=l;i<=r;i=suf[i])

		while(nxt[i])

		{

			if(nxt[i]>r)Fail();

			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)Fail();

	for(int i=suf[l];i<=r;i=suf[i])if(!a[i]&&cnt<sum)a[i]=get(),++cnt;

	if(sum==1&&cnt==0)a[l]=get();

	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[i]]&&!a[suf[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();m=n+n-1;

	for(int i=1;i<=m;++i)a[i]=read();

	if(a[1]&&a[m]&&a[1]!=a[m])Fail();

	a[1]=a[m]=a[1]|a[m];

	for(int i=0;i<=m;++i)pre[i]=i-1,suf[i]=i+1;

	for(int i=m;i;--i)if(a[i])nxt[i]=vis[a[i]],vis[a[i]]=i;

	Solve(1,m);

	puts("yes");for(int i=1;i<=m;++i)printf("%d ",a[i]);

	puts("");return 0;

}

巴特西

【CF1053E】Euler tour

【CF1053E】Euler tour

题面

题解

最新文章

热门文章