输入

输出

样例输入

1 2 3 0 3 5

样例输出

YES 2

数据范围

20%做法

bfs，加一些优化，或者用IDA*，双向广搜。

100%做法

对于每一次使用技能有哪些情况呢？

我们看一下图片

其实每一次使用技能就只有4种情况。

分别就是：中间的向两边跳，还有两边向中间跳。

因为这些转移时可逆的，

所以，我们只需要做从中间向两边跳的操作。

我们设一个三元组(x,y,z)

为了方便转移，我们再设多两个变量，

l = y-x

r = z-y

那么，中间向两边跳 (x, y, z) - (x-l, y-l, z), (x, y, z) - (x, y-z, z-r)

若就原来的状态设为转移出来的两个状态的父亲，

这样，所有的状态就变成了一棵树。

现在问题就变成了在一棵树上面，求两个点的距离。

如果这两个点到根的路径都没有交集，

那么答案就是“NO”

现在我们考虑如何快速找到这两个状态的根？

我们将这个三元组转换一下，

尝试用一个二元组来替换。

我们设这个二元组为(l,r)

那么它的父亲是什么呢？

显然，它的父亲就是(l-r,r)

但是如果一个个向上跳，就会超时。

我们再观察一下这个二元组，

看它的转移方式，有点像更相减损术。

现在就可以通过辗转相除法的思想来做，

所以时间复杂度就变成了log了。

对于求距离，就运用了LCA的思想。

现将它变为同一深度，

然后二分查找向上跳多少步就可以了。

code(c++)

#include <cstdio> #include <algorithm> #include <cstring> #include <string.h> #include <cmath> #include <stdlib.h> #include <math.h> using namespace std; struct arr { int g[8]; } a,b; int ans,len1,len2; bool cmp(int x,int y) { return x<y; } bool pd(arr a,arr b) { for(int i=1;i<=3;i++) if(a.g[i]!=b.g[i])return 0; return 1; } arr get(arr a,int lim,int &sum) { int l=a.g[2]-a.g[1],r=a.g[3]-a.g[2],m; if(!lim||(l==r))return a; if(l<r) { m=min(lim,(r-1)/l); a.g[1]+=m*l; a.g[2]+=m*l; } else { m=min(lim,(l-1)/r); a.g[2]-=m*r; a.g[3]-=m*r; } sum+=m; return get(a,lim-m,sum); } int main() { scanf("%d%d%d",&a.g[1],&a.g[2],&a.g[3]); scanf("%d%d%d",&b.g[1],&b.g[2],&b.g[3]); sort(a.g+1,a.g+4,cmp); sort(b.g+1,b.g+4,cmp); if(!pd(get(a,2147483647,len1),get(b,2147483547,len2))) { printf("NO"); return 0; } printf("YES\n"); if(len1>len2) { swap(len1,len2); swap(a,b); } int t=0; b=get(b,len2-len1,t); int l=0,r=len1,ans=-1,mid; while(l<=r) { mid=(l+r)/2; if(pd(get(a,mid,len1),get(b,mid,len2)))r=mid-1; else { ans=mid; l=mid+1; } } printf("%d",t+2*ans+2); }