P5597 【XR-4】复读 思维题 +二叉树合并

题意：

戳这里查看

分析：

由于这是一个无限大的完全二叉树，所以不合法的方案仅存在于跳到根节点的父亲这一种，且由于指令会无限重复，所以我们必须保证指令会使得离开被标记的子树的时候，所有被标记的点已经全部访问完，因为我们不会折返回去向上跳的

那么我们考虑枚举它是经过哪条路径，从哪个点离开整颗子树的，只要保证在走这条路经的同时遍历完所有的点，且由于指令会无限重复，所以我们对于路径上每一个点，将所有的子树求一个形态上的并集，只要使得整个并集能被访问，那么所有的点都会被访问到，最后的答案就是((cnt-1)*2-dep),其中(cnt)是并集的树上节点数，(dep)为我们枚举的离开的点的深度

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	const int maxn = 2e3+5;
	int ans=1e9+7,cnt,cur,rt,pos;
	char ch[maxn],pth[maxn];
	struct tree
	{
		int lc,rc;
	}f[maxn],g[maxn];
	
	void build(int &x)
	{
		if(!x) x=++cnt;
		int t=ch[pos++]-'0';
		if(t&1) build(f[x].lc);
		if(t&2) build(f[x].rc);
	}
	
	void merge(int &x,int y)
	{
		if(!x) x=++cnt;
		if(y==cur) return ;
		if(f[y].lc) merge(g[x].lc,f[y].lc);
		if(f[y].rc) merge(g[x].rc,f[y].rc);
	}
	
	void solve(int u,int dep)
	{
		if(u!=1)
		{
			memset(g,0,sizeof(g));
			cur=cnt=1;
			while(cur)
			{
				const int t=cur;
				for(int i=0;i<dep;i++)
				{
					cur=pth[i]=='l'?f[cur].lc:f[cur].rc;
				}
				merge(rt=1,t);
			}
			ans=min(ans,(cnt-1)*2-dep);
		}
		pth[dep]='l';
		if(f[u].lc) solve(f[u].lc,dep+1);
		pth[dep]='r';
		if(f[u].rc) solve(f[u].rc,dep+1);
	}
	
	void work()
	{
		scanf("%s",ch);pos=0;cnt=1;
		build(rt=1);
		solve(1,0);
		printf("%d
",ans);
	}

}

int main()
{
	zzc::work();
	return 0;
}