70分做法非常容易想到，使用高精度对经过的点编号，令 \(pos\) 为点的编号，初始为 \(1\) ，则：
1：\(pos<<=1\)2：\(pos<<=1|1\)U：\(pos>>=1\)L：\(pos--\)R：\(pos++\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1e18;
int ans=inf,dx,dy;
string s;
struct BIG_INT{
int len;
short a[N];
BIG_INT(){len=1;memset(a,0,sizeof a),a[1]=1;}
short& operator[](int x) {return a[x];}
BIG_INT operator+(BIG_INT b)
{
BIG_INT c;
int l=max(len,b.len);
int jw=0;
for (int i=1;i<=len;i++)
{
int now=a[i]+b[i]+jw;
c[i]=now%10,jw=now/10;
}
c.len=l;
while (jw) c[++c.len]=jw%10,jw/=10;
return c;
}
friend int comp(BIG_INT x,BIG_INT y)
{
if (x.len!=y.len) return x.len<y.len;
for (int i=x.len;i>=1;i--) if (x[i]!=y[i]) return x[i]<y[i];
return -1;
}
friend int operator-(BIG_INT x,BIG_INT y)
{
if (comp(x,y)==1) swap(x,y);
int ret=0;
int jw=0,nw=1;
for (int i=1;i<=x.len;i++)
{
int now=x[i]+jw;
if (now<y[i]) jw=-1,now+=10;
else jw=0;
ret+=nw*(now-y[i]);
nw*=10;
if (i>=18) break;
}
return ret;
}
void operator -- ()
{
int now=1;
while (a[now]==0) a[now]=9,now++;
a[now]--;
if (now==len&&a[now]==0) len--;
}
void operator ++ ()
{
int now=1;
while (now<=len&&a[now]==9) a[now]=0,now++;
a[now]++;
if (now==len+1) len=now;
}
BIG_INT operator/(int x)
{
BIG_INT c;
int jw=0;
for (int i=len;i>=1;i--)
{
int now=a[i]+jw;
c[i]=now/2;
jw=now&1;
jw*=10;
}
c.len=len;
while (c[c.len]==0) c.len--;
return c;
}
}x,y;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s;
for (char c:s)
{
if (c=='1') dx++,x=x+x;
else if (c=='2') dx++,x=x+x,x.operator++();
else if (c=='U') dx--,x=x/2;
else if (c=='L') x.operator--();
else x.operator++();
}
cin>>s;
for (char c:s)
{
if (c=='1') dy++,y=y+y;
else if (c=='2') dy++,y=y+y,y.operator++();
else if (c=='U') dy--,y=y/2;
else if (c=='L') y.operator--();
else y.operator++();
}
if (dx>dy) swap(x,y),swap(dx,dy);
int tot=0;
while (dy!=dx)
{
dy--;
tot++;
y=y/2;
}
ans=y-x+tot;
while (comp(x,y)!=-1)
{
tot+=2;
x=x/2,y=y/2;
ans=min(ans,y-x+tot);
}
ans=min(ans,tot);
cout<<ans;
}
下面讲满分做法
考虑用数组存储路径。
1：\(a_{++len}=0\)2：\(a_{++len}=1\)U：\(jw(len--)\)L：\(a_{len}--\)R：\(a_{len}++\)
其中的 \(jw(x)\) 是向前一步进位，可以发现 \(a\) 数组中存的每一位都变成了上下节点间的移动，没有了左右的移动，于是就有了 \(jw(x)\) 的写法。
inline void jw(int x)
{
a[x-1]+=(a[x]>>1);//x这一层的贡献映射到上一层就是a[x]/2
a[x]&=1;
}
注意最后要对全局进行一次进位。
现在操作已经都存下来了，那么接下来就是算答案了。
有以下代码：
//la为a操作的大小
//lb为b操作的大小
len=min(la,lb);
int now=0;
for (int i=0;i<=len&&abs(now)<=inf;i++)
{
now=(now<<1)+a[i]-b[i];//计算两个棋子在当前这一层的间距
ans=min(ans,abs(now)+(len-i<<1));//两个还要共同向下跳len-i层
}
cout<<ans+abs(la-lb);//更深的棋子还要单独往下跳
那么这道题就做完了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+5,inf=1e9;
char s[N];
int a[N],la,lb,b[N],ans=inf;
inline void jwa(int x)
{
a[x-1]+=(a[x]>>1);
a[x]&=1;
}
inline void jwb(int x)
{
b[x-1]+=(b[x]>>1);
b[x]&=1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s+1;
int len=strlen(s+1);
for (int i=1;i<=len;i++)
{
if (s[i]=='1') a[++la]=0;
else if (s[i]=='2') a[++la]=1;
else if (s[i]=='U') jwa(la),la--;
else if (s[i]=='L') a[la]--;
else a[la]++;
}
cin>>s+1;
len=strlen(s+1);
for (int i=1;i<=len;i++)
{
if (s[i]=='1') b[++lb]=0;
else if (s[i]=='2') b[++lb]=1;
else if (s[i]=='U') jwb(lb),lb--;
else if (s[i]=='L') b[lb]--;
else b[lb]++;
}
for (int i=la;i>1;i--) jwa(i);
for (int i=lb;i>1;i--) jwb(i);
len=min(la,lb);
int now=0;
for (int i=0;i<=len&&abs(now)<=inf;i++)
{
now=(now<<1)+a[i]-b[i];
ans=min(ans,abs(now)+(len-i<<1));
}
cout<<ans+abs(la-lb);
return 0;
}