考虑一个状态(a,b,c)的转移
b可以往左右跳
或者a和c中离b比较近的往中间跳
如果把当前状态看成一个节点
那么可以吧b往左右跳的情况看成当前节点的左右儿子状态
而且左右儿子状态要到父节点的状态就只能往中间跳，只有唯一的方法
那么所有可以互相转移的状态一起构成了一颗二叉树
树根就是不能往中间跳的状态
当a和c到b的距离一样时就不能往中间跳了
如果状态(a,b,c) 能跳到 (x,y,z) 那么他们就一定要在同一颗树上（即树根相同）
考虑状态(a,b,c) 怎么走到树根
一步一步走肯定会超时
因为题目说棋子是没有区别的
所以a往b跳 2*l 的距离相当于 a 和 b 同时右移 l 的距离
当 Lab < Lbc 时每次跳 Lab 的距离
相当于最终跳了 k 步，使得 Lbc - k*Lab < Lab
那么最后Lbc 就变成了 Lbc%Lab（自己画图理解一下）
那么当 Lbc!=Lab 时，我们每次把距离大的跳成距离小的(Lbc%=Lab)，原本距离小的就大了
然后再反过来跳(Lab%=Lbc)，一直到Lbc==Lab
复杂度就是 gcd 的复杂度O(logL)
如果最后的状态一样那么就有解
考虑如何找最小的步数
两点在一颗树上的最小距离可以用LCA搞
我们也用差不多的方法
先让深的点跳到同一深度
然后二分跳的步数
具体实现看代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int INF=1e9+7; int a,b,c,x,y,z; inline void pre(int &x,int &y,int &z)//预处理，让点从小到大排列 { x+=INF; y+=INF; z+=INF;//可能有负数，为了好理解全部搞成正数 if(y>z) swap(y,z); if(x>y) swap(x,y); if(y>z) swap(y,z); } int xx,yy,zz,dep;//最终的状态 int mx;//二分限制的最大步数 void dfs(int x,int y,int z,int step) { int d1=y-x,d2=z-y; //如果到了根或者到了限制的步数 if(step==mx||d1==d2) { xx=x; yy=y; zz=z; dep=step; return; }//保持一下到达的状态和步数并返回 if(d1>d2)//对两种情况分开来讨论 { swap(d1,d2); int d=d2/d1; if(d2%d1==0) d--;//注意特判 if(step+d<=mx)//如果没到达最大步数 dfs(x,y-d*d1,z-d*d1,step+d); else//如果超过最大步数就只能走mx-step步 { int k=mx-step; dfs(x,y-k*d1,z-k*d1,mx); } } else//跟上面差不多 { int d=d2/d1; if(d2%d1==0) d--; if(step+d<=mx) dfs(x+d*d1,y+d*d1,z,step+d); else { int k=mx-step; dfs(x+k*d1,y+k*d1,z,mx); } } } int main() { int aa,bb,cc,dd; cin>>a>>b>>c; pre(a,b,c); cin>>x>>y>>z; pre(x,y,z); mx=INF;//找根是否相等 dfs(a,b,c,0); aa=xx; bb=yy; cc=zz; dd=dep;//保存一波状态 dfs(x,y,z,0); if(xx!=aa||yy!=bb||zz!=cc) { printf("NO"); return 0; } printf("YES "); int ans=0; if(dd>dep)//先让深度深的跳到同一深度 { ans=dd-dep; mx=dd-dep;//跳dd-dep步就可以使深的点跳到同样深度 dfs(a,b,c,0); a=xx; b=yy; c=zz; } if(dd<dep) { ans=dep-dd; mx=dep-dd; dfs(x,y,z,0); x=xx; y=yy; z=zz; } //二分步数 int l=0,r=INF; while(l<=r) { mx=(l+r)>>1; dfs(a,b,c,0); aa=xx; bb=yy; cc=zz; dfs(x,y,z,0); if(aa!=xx||bb!=yy||cc!=zz) l=mx+1; else r=mx-1; } printf("%d",(l<<1)+ans); return 0; }