题解 P5597 【【XR-4】复读】

· · 题解

不错的思维题。写了一下发现跑得还比较快，来写篇题解。

设运行第一遍指令后机器人走到的结点为 u。

因为当机器人在根节点处运行指令，机器人不会跑到根节点以上；所以当机器人在 u 时再运行指令，机器人也不会跑到 u 以上。

也就是说，第一遍运行指令的时候，就要把 u 以外的宝藏（图中蓝色）全挖出来。

同理，以 u 为结点再运行一遍指令，设机器人走到了 v。显然，v 相对于 u 的位置和 u 相对于根的位置是一样的。

根据刚才的分析，这第二次运行指令，也要把 u 子树里，v 子树外的宝藏（图中红色）都挖掉。

以此类推，第三次运行指令要把绿色的宝藏都挖掉。

但是指令是不能变的。

所以要把图中蓝框、红框、绿框中的树叠加在一起。

一次指令需要把整棵新树都遍历一遍，并停在黑色点上。

除了根到黑点之间这段路只用走一遍外，别的边都要走两边。这样都能算出指令的长度。

枚举 u，取指令最小值即可。

实现

实现并不很简单，而且我的实现比较短，所以讲一下。

因为计算指令长度时需要根到 u 的距离，所以不妨用搜索枚举 u。

建新树时也搜索，需要同时保存在原树上的位置和在新树上的位置。
如果原树的结点在新树上没有，新建新树结点即可。
如果在新树上走到了黑点，就把新树上的位置挪到根。

#include<bits/stdc++.h>
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;
}