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

作者: wjyyy 分类: LCA,二分,倍增,构造,,模拟,解题报告 发布时间: 2018-06-27 17:30

点击量:25

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

 

题目描述

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

我们用跳跳棋来做一个简单的游戏:棋盘上有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向左。ac最多只有一种情况,因为不能连续跳过两个棋子,同一个点也不能同时有两颗棋子,那么b是无论如何都可以移动的,当bac的距离相等时,ac都不能跳:

 

111

   那么我们只考虑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很接近,zx,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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */