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