P5513 [CEOI2013] Board CWOI1114C

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;
}