P5597 【XR-4】复读

题目背景

赛时提醒：当机器人在这棵完全二叉树的根时，执行 U 是非法的，即你需要保证不可能出现这种情况。

赛时提醒：这棵二叉树是无限向下延伸的，即所有节点均有左子节点与右子节点，除了根的所有节点均有父亲。

题目描述

小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：

• L：命令机器人向当前节点的左子走；
• R：命令机器人向当前节点的右子走；
• U：命令机器人向当前节点的父亲走（若没有，则命令非法）。

录入指令后，复读机将会把指令无限复读下去。比如命令为 LR，那么机器人会遵从 LRLRLRLR... 一直走下去。

这棵完全二叉树上有一个 个节点的连通块，保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏，机器人到达过的地方如果有宝藏，则会将其开采。如果一个地方没有宝藏，机器人也可以到那里去。机器人也可以反复经过一个地方。

显然，这个连通块本身也是一棵二叉树。

现在，有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历，小 X 需要寻找到一条尽量短的指令，使得机器人能够挖掘出所有宝藏。

输入格式

一行一个字符串，由 0123 中的字符组成，表示埋有宝藏的这棵二叉树的前序遍历。

• 0：表示这是一个没有儿子的节点。
• 1：表示这是一个只有左子的节点。
• 2：表示这是一个只有右子的节点。
• 3：表示这是一个既有左子又有右子的节点。

输出格式

一个整数，表示最短指令的长度。

输入输出样例 #1

输入 #1

1313000

输出 #1

3

输入输出样例 #2

输入 #2

333003003300300

输出 #2

15

说明/提示

【样例 1 说明】

一种可行的最短指令为 LRU。

本题采用捆绑测试。

• Subtask 1（31 points）：。
• Subtask 2（32 points）：。
• Subtask 3（37 points）：无特殊限制。

对于 的数据，。

很巧妙的一道题目，我也是看了题解才做出来的。

首先，根据输入的先序遍历字符串还原出有宝藏的树Tre1。

然后，我们要确定一个回环Tre2，满足n个Tre2连接可以完全覆盖Tre1.而指令数就等于Tre2的节点数-深度-2.

这里，再分别的选择Tre1上的节点为回环的尾点，Tre1上的根节点为回环的头结点。依次分节遍历和探索。最终构建出来。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
using namespace std;

struct node{
	int ls,rs;
}tre1[2010],tre2[2010];//原树，新树
int cnt1,cnt2,pos1,pos2,ans=1e9;//原树大小，新树大小，原树上 u 的位置，新树上黑点位置,ans
int input(){
	int c=getchar()-'0',u=++cnt1;
	if(c&1) tre1[u].ls=input();
	if(c&2) tre1[u].rs=input();
	return u;
}
void dfs2(int u,int v){//原树位置，新树位置
	if(u==pos1||v==pos2) { pos2=v; v=1; }//到了黑点
	if(tre1[u].ls){
		if(!tre2[v].ls) tre2[v].ls=++cnt2;//新建结点
		dfs2(tre1[u].ls,tre2[v].ls);
	}
	if(tre1[u].rs){
		if(!tre2[v].rs) tre2[v].rs=++cnt2;
		dfs2(tre1[u].rs,tre2[v].rs);
	}
}
void dfs1(int u,int dep){//dep 深度
	pos1=u;
	memset(tre2,0,sizeof tre2);//清空
	pos2=0;
	dfs2(1,cnt2=1);
	ans=min(ans,cnt2*2-2-dep);
	if(tre1[u].ls) dfs1(tre1[u].ls,dep+1);
	if(tre1[u].rs) dfs1(tre1[u].rs,dep+1);
}
int main(){
	input();
	dfs1(1,0);
	cout<<ans<<endl;
	return 0;
}