2144: 跳跳棋
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1291 Solved: 632
[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
0 3 5
Sample Output
YES
2
【范围】
100% 绝对值不超过10^9
2
【范围】
100% 绝对值不超过10^9
HINT
Source
试题分析
神仙题啊！！
对于三元组$(a,b,c)$，发现跳法就只要$3$种，外面的往中间跳，中间往外面的跳。那这不就是一颗树吗，$(a,b,c)$为根，左节点为$(2a-b,a,c)$，右节点为$(a,c,2c-b)$，而且会发现就比如·用左节点距离难道不是$(a,b)$平移$a-b$吗，那么对于$(1,999999,1000000)$往上跳时就可以快速跳了，就像求解$gcd$一样，那么若为$NO$的话，那么两点对应的祖先是不同的，而祖先是无法再往里收缩边界的。然后用两者对于祖先的向对距离就像用倍增lca一样先把两点拉到统一深度上，然后二分判断。
主要在于在树上没有两个相等的$(a,b,c)$，因为若有把他们往上拉时，一定会两者在同一子树上，但是每次往左或右节点都会扩大边界，所以与假设矛盾。
#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<ctime> #include<algorithm> #define int long long #define st pair<node,int> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } struct node{ int x,y,z; }s,t; int ch[4]; void init(){ for(int i=1;i<=3;i++) ch[i]=read(); sort(ch+1,ch+4); s.x=ch[1],s.y=ch[2],s.z=ch[3]; for(int i=1;i<=3;i++) ch[i]=read(); sort(ch+1,ch+4); t.x=ch[1],t.y=ch[2],t.z=ch[3]; } st find(int x,int y,int z){ int deep=0,d1=y-x,d2=z-y; while(d1!=d2){ d1=y-x,d2=z-y; if(d1<d2){ int step=d2/d1; if(d2%d1==0){ x+=(step-1)*d1,y+=(step-1)*d1; deep+=(step-1); }else{ x+=step*d1;y+=step*d1; deep+=step; } }else{ int step=d1/d2; if(d1%d2==0){ y-=(step-1)*d2;z-=(step-1)*d2; deep+=(step-1); }else{ y-=step*d2;z-=step*d2; deep+=step; } } } node k;k.x=x,k.y=y,k.z=z; return make_pair(k,deep); } node get(int x,int y,int z,int deep){ int d1=y-x,d2=z-y; while(d1!=d2&&deep!=0){ d1=y-x,d2=z-y; if(d1<d2){ int step=d2/d1; if(d2%d1==0){ if(step-1<=deep){ deep-=(step-1); x+=(step-1)*d1,y+=(step-1)*d1; }else{ x+=deep*d1;y+=(deep*d1);deep=0;break; } }else{ if(step<=deep){ deep-=step; x+=step*d1,y+=step*d1; }else{ x+=deep*d1,y+=deep*d1;deep=0;break; } } }else{ int step=d1/d2; if(d1%d2==0){ if(step-1<=deep){ deep-=(step-1); y-=(step-1)*d2,z-=(step-1)*d2; }else{ y-=deep*d2,z-=deep*d2;deep=0;break; } }else{ if(step<=deep){ deep-=step; y-=step*d2,z-=step*d2; }else{ y-=deep*d2,z-=deep*d2;deep=0; break; } } } } node k;k.x=x,k.y=y,k.z=z; return k; } int ans=0; bool same(node x1,node x2){return x1.x==x2.x&&x1.y==x2.y&&x1.z==x2.z;} int l,r,minn=INT_MAX; void check(){ int tot=0; while(1){ ch[1]=rand(),ch[2]=rand(),ch[3]=rand(); if(ch[1]==ch[2]||ch[1]==ch[3]||ch[2]==ch[3]){continue;} sort(ch+1,ch+4);int x=ch[1],y=ch[2],z=ch[3]; st p1=find(x,y,z); node k=p1.first; if(same(k,get(x,y,z,p1.second))){printf("AC %d ",++tot);} else{ printf("WA");exit(0); } } } signed main(){ init(); st p1=find(s.x,s.y,s.z);node k1=p1.first;int deep1=p1.second; st p2=find(t.x,t.y,t.z);node k2=p2.first;int deep2=p2.second; if(!same(k1,k2)){printf("NO ");return 0;} printf("YES "); if(deep1<deep2){ans+=deep2-deep1;node k=get(t.x,t.y,t.z,deep2-deep1);t.x=k.x,t.y=k.y,t.z=k.z;} else if(deep1>deep2){ans+=deep1-deep2;node k=get(s.x,s.y,s.z,deep1-deep2);s.x=k.x,s.y=k.y,s.z=k.z;} l=0,r=(deep1+deep2)<<1; while(l<=r){ int mid=l+r>>1; if(same(get(s.x,s.y,s.z,mid),get(t.x,t.y,t.z,mid))){r=mid-1;minn=min(minn,mid);} else l=mid+1; }printf("%d ",2*minn+ans); }