一本通1559跳跳棋

1559：跳跳棋

时间限制: 1000 ms 内存限制: 524288 KB

原题来自：BZOJ 2144

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

第一行包含三个整数，表示当前棋子的位置

如果无解，输出一行 NO。如果可以到达，第一行输出 YES，第二行输出最少步数。

样例输入

1 2 3
0 3 5

样例输出

YES
2

对于

对于 $10^9109。保证 a,b,c 互不相同，x,y,z 互不相同。$

不得不说这题真是tm坑爹想法题，好写不好想考场上很难A掉

如果单纯排列搞一搞貌似有6种走法，但是因为棋子跳的时候只能越过一个棋子，所以对于任意一个状态，它最多只有3种走法。

假设三个点已经从小到大排好，显然中间的棋子无论往左跳还是往右跳都只要越过一个棋子。

考虑最左边的棋子，它不可能直接越过中间和右边的棋子。右边同理。

现在问题来了。两边的棋子越过中间的点是否会直接越过两个点呢？

以2、3、7为例：

2跳过3到达4，是不会超过7的。

但是7越过3到达-1，显然超过了2。所以它跳过了两个棋子，这是不合法的。

这样就得到了结论：只有离中间更近的棋子才可以跳进去。那么确实是最多只有3种情况。

为什么是最多呢？因为还有两边与中间的距离一样近的情况，这样左右都跳不了了，只有中间的可以跳出去。比如3、5、7。

很容易发现，从只有两种跳法的所有状态出发，就可以到达任意一种状态。

什么意思呢？这是一棵二叉树。从2、4、6这样的状态出发，只能4往左右走。把拓展的状态作为左右儿子。左边0、2、6，右边2、6、8。在这两个状态中，如果我们从两边往中间走，显然就还原为父亲节点的状态了。这样是没有意义的。于是只好再从中间完两边走，然后又变成二叉树……于是所有的状态就表示成了以形如等差数列三项的状态为根构成的森林。

这样一来，只要知道两个状态所在的树根是不是一样就可以判断是否有解。具体解的大小可以LCA搞定，或者直接二分答案

假设三个数a、b、c，b-a=t1，c-b=t2。不妨设t1<t2。我们的目标就是把a、c往中间移，最终使得t1=t2。

那么显然a往中间跳的次数就是(t1-1)/t2，之后t1,t2的大小关系就会变

而且a、b、c是不计顺序的，所以直接a+=t1*(t1-1)/t2 b+=t1*(t1-1)/2 就好了

时间复杂度大概和gcd是同级的，每次logn

#include <bits/stdc++.h>
using namespace std;
const int inf=1000000000;
struct Record
{
    int a[5];
}Start,End;
int Depth=0;
inline Record Jump(Record Now,int Step)
{
    Record tmp=Now;
    int t1=Now.a[2]-Now.a[1],t2=Now.a[3]-Now.a[2];
    if(t1==t2) return tmp;
    if(t1<t2)
    {
        int t=min(Step,(t2-1)/t1);
        Step-=t; Depth+=t;
        tmp.a[1]+=t*t1; tmp.a[2]+=t*t1;
    }
    else
    {
        int t=min(Step,(t1-1)/t2);
        Step-=t; Depth+=t;
        tmp.a[2]-=t*t2; tmp.a[3]-=t*t2;
    }
    return (Step)?(Jump(tmp,Step)):(tmp);
}
inline bool operator !=(Record p,Record q)
{
    int i;
    for(i=1;i<=3;i++) if(p.a[i]!=q.a[i]) return 1;
    return 0;
}
int main()
{
    int i,D_Start,D_End,ans=0;
    for(i=1;i<=3;i++) scanf("%d",&Start.a[i]); sort(Start.a+1,Start.a+4);
    for(i=1;i<=3;i++) scanf("%d",&End.a[i]); sort(End.a+1,End.a+4);
    Record Last1=Jump(Start,inf); D_Start=Depth; Depth=0;
    Record Last2=Jump(End,inf); D_End=Depth; Depth=0;
    if(Last1!=Last2) return 0*puts("NO");
    if(D_Start>D_End) {swap(Start,End); swap(D_Start,D_End);}
    ans=D_End-D_Start;
    Record pp=Jump(End,ans);
    End=pp;
    int l=0,r=D_Start;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        (Jump(Start,mid)!=Jump(End,mid))?(l=mid+1):(r=mid-1);
    }
    puts("YES");
    printf("%d
",ans+2*l);
    return 0;
}

View Code