description

洛谷P5513

solution

用一个二进制数维护这个节点所处的位置，那么"1"操作就是这个数\(*2\)，"2"操作就是这个数\(*2+1\)，"L"操作就是这个数\(-1\)，"R"操作就是这个数\(+1\)，但直接维护，每次"L""R"操作都暴力进位，就会被反复横跳（即不断地进行\("L""R"\)）的数据卡掉，于是我们可以不进位，将\(+1、-1\)的标记记在目前的最后一位上，"U"操作时进位，操作结束后再从后往前扫一遍依次进位即可。确定了节点的位置，那么求出最短距离就很简单了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s1[N],s2[N];
int len1,len2,ch1[N],ch2[N],dep1,dep2;
int main(){
    scanf("%s%s",s1+1,s2+1);
    len1=strlen(s1+1);len2=strlen(s2+1);
    for(int i=1;i<=len1;++i){
        if(s1[i]=='1') ch1[++dep1]=0;
        else if(s1[i]=='2') ch1[++dep1]=1;
        else if(s1[i]=='L') --ch1[dep1];
        else if(s1[i]=='R') ++ch1[dep1];
        else if(s1[i]=='U'){
            ch1[dep1-1]+=ch1[dep1]>>1;
            --dep1;
        }
    }
    for(int i=dep1;i>=1;--i){
        ch1[i-1]+=ch1[i]>>1;
        ch1[i]=abs(ch1[i])%2;
    }
    for(int i=1;i<=len2;++i){
        if(s2[i]=='1') ch2[++dep2]=0;
        else if(s2[i]=='2') ch2[++dep2]=1;
        else if(s2[i]=='L') --ch2[dep2];
        else if(s2[i]=='R') ++ch2[dep2];
        else if(s2[i]=='0'){
            ch2[dep2-1]+=ch2[dep2]>>1;
            --dep2;
        }
    }
    for(int i=dep2;i>=1;--i){
        ch2[i-1]+=ch2[i]>>1;
        ch2[i]=abs(ch2[i])%2;
    }
    int ans=0;
     while(dep1>dep2) --dep1,++ans;
     while(dep2>dep1) --dep2,++ans;
     int ans1=dep1*2,p=dep1,ans2=0,pos;
     for(int i=1;i<=dep1;++i){
         if(ch1[i]==ch2[i]) ans1-=2;
         else{
             p=i;
             if(ch1[i]<ch2[i]) pos=1;
             else pos=2;
             break;
        }
    }
     for(int i=p;i<=dep1;++i){
         ans2<<=1;if(ans2>=ans1+dep1-p+1) break;
         if(ch1[i]<ch2[i]){
            if(pos==1) ++ans2;
            else --ans2;
            if(ans2>=ans1+dep1-p+1) break;
        }
        if(ch1[i]>ch2[i]){
            if(pos==1) --ans2;
            else ++ans2;
            if(ans2>=ans1+dep1-p+1) break;
        }
        ans1=min(ans1,ans2+(dep1-i)*2);
    }
     printf("%d\n",ans+min(ans1,ans2));
    return 0;
}