【LCA】bzoj 2144:跳跳棋

2144: 跳跳棋

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 248 Solved: 121
[Submit][Status][Discuss]

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

　　暴力广搜有20分。。

　　我们转化一下问题。。

　　一次操作分为两种情况: 1)中间的棋子跳 2)两边的棋子中的一个跳(一次只允许跳过1颗棋子)。

　　我们可以进一步转化模型

　　样例中的图就是两边的棋子跳。

　　我们发现这样相当于是中间的跳出来。。

　　所以我们设中间跳两边为该状态节点的两个儿子。

　　而两边跳中间是该节点的父亲节点。

　　然后树上暴力有40.

　　100: 先找两种状态的最终祖先(两边到中间距离相等(没有父节点))。

　　然后如果最终祖先不等则NO

　　相等那么把深度大的先提到同一深度

　　然后LCA

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 inline int in()
 9 {
10     int x=0,f=1;char ch=getchar();
11     while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
12     if(ch=='-')f=-1,ch=getchar();
13     while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
14     return x*f;
15 }
16 
17 struct data{
18     int a[5];
19 };
20 
21 int a[5],b[5],tem=0;
22 
23 data up(int c[],int k)
24 {
25     data t;
26     int t1=c[2]-c[1],t2=c[3]-c[2];
27     for(int i=1;i<=3;i++)t.a[i]=c[i];
28     if(t1==t2)return t;
29     else if(t1<t2)
30     {
31         int ans=min(k,(t2-1)/t1);
32         tem+=ans;k-=ans;
33         t.a[1]+=ans*t1,t.a[2]+=ans*t1;
34     }
35     else
36     {
37         int ans=min(k,(t1-1)/t2);
38         tem+=ans,k-=ans;
39         t.a[2]-=ans*t2,t.a[3]-=ans*t2;
40     }
41     if(k)return up(t.a,k);
42     else return t;
43 }
44 
45 bool operator!=(data a,data b)
46 {
47     for(int i=1;i<=3;i++)if(a.a[i]!=b.a[i])return 1;
48     return 0;
49 }
50 
51 int main()
52 {
53     for(int i=1;i<=3;i++)a[i]=in();
54     for(int j=1;j<=3;j++)b[j]=in();
55     sort(1+a,1+a+3);
56     sort(1+b,1+b+3);
57     data t1=up(a,1e9);int d1=tem;tem=0;
58     data t2=up(b,1e9);int d2=tem;tem=0;
59     if(t1!=t2){
60         printf("NO");
61         return 0;
62     }
63     if(d1>d2)
64     {
65         swap(d1,d2);
66         for(int i=1;i<=3;i++)swap(a[i],b[i]);
67     }
68     int ans=d2-d1;
69     t1=up(b,ans);
70     for(int i=1;i<=3;i++)b[i]=t1.a[i];
71     int l=0,r=d1,res;
72     while(l<=r)
73     {
74         int mid=(l+r)>>1;
75         if(up(a,mid)!=up(b,mid))l=mid+1;
76         else r=mid-1,res=mid;
77     }
78     printf("YES
");
79     printf("%d",ans+2*res);
80     return 0;
81 }

View Code