P5597 【XR-4】复读 题解

一道思维题，我自己没能想出来，研究了很久，最后参考了题解想了很久才做出来，但题解写得比较简略，于是在此记录一下。

---

解题思路

• 因为是无限延伸的完全二叉树，所以只要不对树根进行U操作，所有的命令都是合法的。

• 因为是无限复读指令，所以每一次执行指令之后的相对的位移是一样的。

• 于是，可以将要遍历的整棵树分成几个相同（也可以有包含关系）且连续的部分（这样可以用重复执行相同指令串来处理），然后处理每一个部分的过程就是要求出的指令串。

• 每一部分的具体操作中一定会遍历起点到终点的边一遍和其他的边两遍，于是有 $tot = 2 \times ( sum - 1 ) - d $（ $tot$ 是步骤数， $sum$ 是点数， $d$ 是起点到终点的边数），具体参考图片：

• 然后，考虑分部分的方法，可以进行 $O(n)$ 的暴力枚举

• 具体操作时，涉及到对所有部分的合并，如将下图中的A树拆分成B的形状，为了使指令串可以处理所有的部分，应将所有部分合并成C，然后找出C的处理步骤数，就是这一拆分下的答案。

• 最终，答案是所有拆分方法答案中的最小值。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+100;
int n,l[maxn],r[maxn];
int tmp_l[maxn],tmp_r[maxn];
//tmp_l[],tmp_r[]是合并后的图
int sum,cur,ans=0x3f3f3f3f;
//sum是一个拆分中的答案
//cur在后面作为每一部分的终点
//ans是总答案
char p[maxn];
//保存拆分路径
int read(){
	//根据前序遍历建树
	char tmp;
	int now;
	cin>>tmp;
	n++;
	now=n;
	if(tmp=='1'||tmp=='3')
		l[now]=read();
	if(tmp=='2'||tmp=='3')
		r[now]=read();
	return now;
}
void merge(int &x,int y){
	//合并各个部分
	if(x==0)sum++,x=sum;
	//新建一个点
	if(y==cur)return;
	//到达这部分终点，退出
	if(l[y]!=0)merge(tmp_l[x],l[y]);
	if(r[y]!=0)merge(tmp_r[x],r[y]);
	//合并左右子树
}
void solve(int u,int d){
	//u是当前部分的结束位置的下一个位置
	//d是当前部分的长度
	if(u!=1){
		memset(tmp_l,0,sizeof(tmp_l));
		memset(tmp_r,0,sizeof(tmp_r));
		//清空
		sum=1;
		//开始时只有根节点
		cur=1;
		while(cur){
			int t=cur;
			for(int i=0;i<d;i++){
				cur=(p[i]=='l'?l[cur]:r[cur]);
				//按照路径找终点
			}
			int tmp_x=1;
			merge(tmp_x,t);
			//合并树，求sum
		}
		ans=min(ans,(sum-1)*2-d);
		//记下答案
	}
	p[d]='l';
	if(l[u])
		solve(l[u],d+1);
	//递归向左子树扩展路径
	p[d]='r';
	if(r[u])
		solve(r[u],d+1);
	//递归向右子树扩展路径
}
int main(){
	read();
	solve(1,0);
	cout<<ans<<endl;
	return 0;
}