【bzoj2144】跳跳棋

2015.01.27 18:54 Tue | 6次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

第一行包含三个整数,表示当前棋子的位置a b c。(互不相同)第二行包含三个整数,表示目标位置x y z。(互不相同)

Output

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

Sample Input

1 2 3
0 3 5

Sample Output

YES
2
【范围】
100% 绝对值不超过10^9

题解

刚开始看,想到的就是宽搜状态,不用说,tle
然后老师说这题像树,我想啊想,差不多建出来个模型,无耻的上网查了题解,发现思路差不多,好吧开写
刚开始wa了一把,后来一看把二分时候的r设成2了……
思路:
把状态设为一颗树,由中间节点跳向两边作为子节点,由两边跳向中间(只能从一边)作为父亲节点,然后在树上进行二分+lca

我的程序

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define inf 1000000000
using namespace std;
int ans,depth;
struct node{
    int num[4];
}a,b;
node get_st(node &a,int k)//从a状态走k次 
{
    sort(a.num+1,a.num+4); 
    node ret;
    int t1=a.num[2]-a.num[1],t2=a.num[3]-a.num[2];//中间节点到两边的距离 
    if(t1==t2) return a;//不能再向上查 
    if(t1<t2)
    {
        int t=min(k,(t2-1)/t1);//最多能在当前状态走多少次 
        k-=t;
        depth+=t;
        ret.num[1]=a.num[1]+t1*t;
        ret.num[2]=ret.num[1]+t1;
        ret.num[3]=a.num[3];
    }
    else
    {
        int t=min(k,(t1-1)/t2);
        k-=t;
        depth+=t;
        ret.num[3]=a.num[3]-t2*t;
        ret.num[2]=ret.num[3]-t2;
        ret.num[1]=a.num[1];
    }
    if(k) return get_st(ret,k);//类似辗转相除 
    else return ret;
}
bool operator == (const node &a,const node &b)
{
    for(int i=1;i<=3;i++)
    if(a.num[i]!=b.num[i]) return 0;
    return 1;
}
bool operator != (const node &a,const node &b)
{
    for(int i=1;i<=3;i++)
    if(a.num[i]!=b.num[i]) return 1;
    return 0;
}
int main()
{
    cin>>a.num[1]>>a.num[2]>>a.num[3]>>b.num[1]>>b.num[2]>>b.num[3];
    sort(a.num+1,a.num+4);
    sort(b.num+1,b.num+4);
    node t1=get_st(a,inf);int d1=depth;//找出初始状态的根节点,并记录深度 
    depth=0;
    node t2=get_st(b,inf);int d2=depth;//找出结束状态的根节点,并记录深度 
    if(t1!=t2) //若根节点不同,显然不能互相到达 
    {
        puts("NO");
        return 0;
    }
    if(d1>d2) a=get_st(a,d1-d2);//调节深度 
    else if(d1<d2) b=get_st(b,d2-d1);//调节深度 
    if(a==b) 
    {
        printf("YES\n%d",d2-d1);
        return 0;
    }
    int l=0,r=inf;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(get_st(a,mid)==get_st(b,mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("YES\n%d",ans*2+d2-d1);
}```