「CEOI2013」Board

description

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;

}

巴特西

「CEOI2013」Board

description

solution

code

最新文章

热门文章