bzoj 2144: 跳跳棋 lca+倍增

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。 写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

绝对值不超过10^9

分析

做法比较牛逼的一道题。

把一个状态表示成(d1,d2,p)的形式，其中d1表示前两个点之间的距离，d2表示后两个点之间的距离，p表示中间点的坐标。

转移的话分两种，一种是两边的点往中间跳，一种是中间的点往两边跳。

如果是中间的点往两边跳，那么转移有

(d1,d2,p)->(d1,d1+d2,p-d1)

(d1,d2,p)->(d1+d2,d2,p+d2)

如果是两边往中间跳，那么分两种情况

若d1 < d2则(d1,d2,p)->(d1,d2-d1,p+d1)

若d1 > d2则(d1,d2,p)->(d1-d2,d2,p-d2)

若d1=d2则没有这种转移。

牛逼之处来了，我们把每个状态看成一个点，往两边跳的两种状态看做其两个儿子，两边往中间跳到的状态看做其父亲。其中若d1=d2则为根节点。注意到一棵树上两个点的路径是唯一的，那么就可以用倍增等各种各样的做法来求距离。

其中这里的更相减损可以用辗转相除来加速。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int t[];
struct data{int d1,d2,p;};

bool operator == (data a,data b)
{
    return a.d1==b.d1&&a.d2==b.d2&&a.p==b.p;
}

int get_dep(data a)
{
    if (a.d1==a.d2) return ;
    int ans;
    if (a.d1>a.d2) ans=(a.d1-)/a.d2,a.d1=(a.d1-)%a.d2+;
    else ans=(a.d2-)/a.d1,a.d2=(a.d2-)%a.d1+;
    return get_dep(a)+ans;
}

data get_kth(data a,int k)
{
    int t;
    while (k)
    {
        if (a.d1==a.d2) break;
        if (a.d1<a.d2) t=min(k,(a.d2-)/a.d1),k-=t,a.d2-=t*a.d1,a.p+=t*a.d1;
        else t=min(k,(a.d1-)/a.d2),k-=t,a.d1-=t*a.d2,a.p-=t*a.d2;
    }
    return a;
}

int main()
{
    for (int i=;i<;i++) scanf("%d",&t[i]);sort(t,t+);
    data a=(data){t[]-t[],t[]-t[],t[]};
    for (int i=;i<;i++) scanf("%d",&t[i]);sort(t,t+);
    data b=(data){t[]-t[],t[]-t[],t[]};
    int w1=get_dep(a),w2=get_dep(b),ans=w1+w2;
    if (w1<w2) swap(w1,w2),swap(a,b);
    a=get_kth(a,w1-w2);w1=w2;
    for (int i=;i>=;i--)
        if (!(get_kth(a,<<i)==get_kth(b,<<i))) a=get_kth(a,<<i),b=get_kth(b,<<i);
    if (!(a==b)) a=get_kth(a,),b=get_kth(b,);
    if (a==b) printf("YES\n%d",ans-*get_dep(a));
    else puts("NO");
    return ;
}