【构造】【二叉树】【LCA】【二分答案】 洛谷P1852 [国家集训队]跳跳棋 题解

点击量：277

   这个题主要考的是建模，也就是构造。

目录

题目描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）

 

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

 

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

 

输入输出格式

输入格式：

第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）

 

第二行包含三个整数，表示目标位置x y z。（互不相同）

 

输出格式：

如果无解，输出一行NO。

 

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

 

输入输出样例

输入样例#1：

1 2 3

0 3 5

输出样例#1：

YES

2

说明

20% 输入整数的绝对值均不超过10

 

40% 输入整数的绝对值均不超过10000

 

100% 绝对值不超过10^9

 

   这个题考的是建模能力，同时也考了建模后的算法。

建模思想：

   对于任意三颗棋子a,b,c，它们最多有3种跳法:b向左，b向右，a向右或c向左。a和c最多只有一种情况，因为不能连续跳过两个棋子，同一个点也不能同时有两颗棋子，那么b是无论如何都可以移动的，当b到a和c的距离相等时，a和c都不能跳：

   那么我们只考虑b向两边跳的情况，因为a,b,c->a,c,b可以看做是原来为a,c,b的棋子布局中，c向右跳了。我们如果把这个c看作例子中的b，其本质是一样的。那么我们每个点有两个方案延伸，结果我们发现最匹配的模型是二叉树。每个点的度为2或3，当度为3时为非根非叶子节点，当度为2时为根节点，此时因为|ab|=|bc|，所以不能通过a,c延伸。而我们在上一段提到的最多三种情况，指向当前节点父亲的操作实际上就是父亲到自己的逆操作。每个节点一定都有孩子，不过有的孩子越了界，没有必要考虑。只要我们向靠近收缩的方向跳，就不会越界。

求解方法：

   既然我们建模出了一棵树，那么树就一定有根（度为2）。当三个点间隔最小时，它们的间隔一定相等，这是充要条件。当两两间隔不相等时，它一定可以使间隔拉得更小，因此间隔是相等的，那么这种状态就是树根。因此如果每个状态是树上的一个节点的话，相互转移就是求树上两点间距离。因此我们要求LCA来计算树上两点间距离，如果不在一棵树内，那么就是NO。那么问题来了，树的深度可能有$ 2\times 10^9$（正负坐标），我们如果直接模拟，就算建图也直接爆了时间空间。因此我们要加速这个过程，避免无关状态。

   想到加速，就能联想到过河（解题报告）这个问题，中间过程的状态实际上是没有必要枚举的。因为在这两个问题中，范围很大，但利用率却很小，并且其中很多状态是没有用的。那么我们设x,y,z中，x,y很接近，z离x,y很远。那么我们每次让x向右跳，更新出一个状态x,y+(y-x),z，我们一直这样下去，每次相当于把x,y向右平移了y-x个单位，我们用z-y除掉这个数，就是我们总共爬到一个比较接近根节点的点所需的步数，再对最后一小段进行处理，并且要注意不能平移到z。

   再考虑到我们只有一组询问，而倍增LCA是很有效的模拟，不需要麻烦的状态转移。并且可以在$ \log N \ N\approx 2^{31}$的时间复杂度内求到LCA，那么我们每次利用倍增的思想二分答案，判断是否到了公共祖先，再把每次向上爬的距离做一个总和记得一起爬的时候要×2太坑了。这个树上距离就是我们要的答案。

Code：

#include<cstdio>

long long ans=0;

long long cal(int x,int y,int z)//求深度
{
    long long ans=0;
    if(y-x==z-y)
        return ans;
    if(y-x<z-y)
    {
        //xy向z跳
        int len=y-x;//跳一次能平移的距离
        int tot=z-y-1;
        int p=tot/len;
        ans+=p;//取整
        x+=p*len;
        y=x+len;
        if(y-x!=z-y)
            ans+=cal(x,y,z);
    }
    else
    {
        //yz向x跳
        int len=z-y;
        int tot=y-x-1;
        int p=tot/len;
        ans+=p;
        z-=p*len;
        y=z-len;
        if(y-x!=z-y)
            ans+=cal(x,y,z);
    }
    return ans;
}

void up(int &x,int &y,int &z,long long k)//把x,y,z修改为跳k次之后的
{
    if(y-x==z-y||k==0)
        return;
    if(y-x<z-y)
    {
        int len=y-x;
        int tot=z-y;
        int p=tot/len;
        if(p<=k)
            k-=p;
        else
        {
            x+=len*k;
            y=x+len;
            return;
        }
        x+=p*len;
        y=x+len;
        up(x,y,z,k);
    }
    else
    {
        int len=z-y;
        int tot=y-x;
        int p=tot/len;
        if(p<=k)
            k-=p;
        else
        {
            z-=k*len;
            y=z-len;
            return;
        }
        z-=p*len;
        y=z-len;
        up(x,y,z,k);
    }
    return;
}
int A,B,C,X,Y,Z;
int a,b,c,x,y,z;
void Init()//初始化出发点
{
    a=A,b=B,c=C,x=X,y=Y,z=Z;
    return;
}
bool check()
{
    return a==x&&b==y&&c==z;//是否公共祖先
}

void sort(int &x,int &y,int &z)//输入可能乱序
{
    int t;
    if(x>y)
    {
        t=x;
        x=y;
        y=t;
    }
    if(y>z)
    {
        t=y;
        y=z;
        z=t;
    }
    if(x>y)
    {
        t=x;
        x=y;
        y=t;
    }
    return;
}
int main()
{
    scanf("%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z);
    sort(a,b,c);
    sort(x,y,z);

    long long dpt1=1+cal(a,b,c);
    long long dpt2=1+cal(x,y,z);
    A=a,B=b,C=c,X=x,Y=y,Z=z;
    Init();
    up(a,b,c,dpt1-1);
    up(x,y,z,dpt2-1);
    if(!check())
    {
        puts("NO");
        return 0;
    }
    Init();
    long long ans=0;
    if(dpt1<dpt2)
    {
        ans=dpt2-dpt1;//单独爬也要计算
        up(x,y,z,dpt2-dpt1);
        dpt2=dpt1;
    }

    if(dpt2<dpt1)
    {
        ans=dpt1-dpt2;
        up(a,b,c,dpt1-dpt2);
        dpt1=dpt2;
    }
    long long l=0,r=dpt1,mid;
    A=a,B=b,C=c,X=x,Y=y,Z=z;//重定义Init
    while(l<r)
    {
        Init();//初始化出发点
        mid=l+r>>1;
        up(a,b,c,mid);
        up(x,y,z,mid);
        if(check())
            r=mid;
        else
            l=mid+1;
    }
    ans+=l;
    printf("YES\n%lld\n",ans);
    return 0;
}