本文共 1929 字，大约阅读时间需要 6 分钟。

题意

给定三元组$(x,y,z)$

每次可以从$x,y,z$任选一个作为对称轴,其余数字可以根据这个对称轴跳到另一侧

规则是不能跨越两个数字

给你两个三元组,判断最短操作步数.

$分析$

这题思路是真的隐蔽…

首先对于三元组$(x,y,z)$

首先$y$可以跳到$x$左侧,也可以跳跃到$z$右侧,这是毫无疑问的

然后,当$y-x<z-y$时,$x$可以跳到$y$右边,因为没有跨过$z$

然后,当$y-x>z-y$时,$z$可以跳到$x$左边,因为没有越过$x$

而且特殊的,当$y-x==z-y$时是特殊点,只能由$y$往左右两侧跳

其实说这么多,就是可以把这些状态看作点,画一棵树

$y$往左跳其实就是往左子树走,$y$往右跳就是往右子树走

而$x$往右跳或$z$往左跳其实就是上一个状态的$y$往左(右)跳形成的

所以这其实是一颗二叉树,只存在$y$往哪边跳而已造成左右分枝

当$y-x==z-y$时是根,因为没有返祖边

$那么第一问就是判断两个状态是否在一棵树里$

可以直接去找每个状态的根节点判断是否相等

因为根节点是$y-x==z-y$

那么当$y-x<z-y$时,说明$x$需要跳到$y$右侧

那么当$y-x>z-y$时,说明$z$要跳到$y$左侧

这样一步一步跳就可以超时了

但是可以加速,观察发现若$x$往右跳,状态转移就是

$(x,y,z)->(x+(y-x),y+(y-x),z)$

所以可以用点数学技巧快速跳跃,详见代码.

然后求最短操作次数,其实就是求树上两点的距离,那么求$lca$就好了

我们无法建树,图太大了

但是我们可以用数学方法跳跃快速求$k$级祖先,那么就二分求$lca$

当$k$级祖先相等,$lca$肯定在下面或这个点

否则在上面

#include 
   
    using namespace std;struct state{
    int x,y,z,d; }Start,End;bool equal(state a,state b){
    return (a.x==b.x)&&(a.y==b.y)&&(a.z==b.z); }void init(state &t ){
   	if( t.x>t.y )	swap(t.x,t.y);//y>x	if( t.y>t.z )	swap(t.y,t.z);//z>y	if( t.x>t.y )	swap(t.x,t.y);}state root(state &now){
   	state t = now;	while( t.z-t.y!=t.y-t.x )	{
   		int p = t.y-t.x, q = t.z-t.y, r;		if( p
    0 )	{
   		int p = t.y-t.x, q = t.z-t.y, r;		if( pdeep2 )	Start=UP(Start,dis);			else	End=UP(End,dis);			int l = 0, r = min( deep1,deep2 ),nice = 0;			while( r>=l )			{
   				int mid = l+r>>1;				if( equal( UP(Start,mid),UP(End,mid) ) )	r=mid-1,nice=mid;				else	l=mid+1;			}			printf("YES\n%d\n",nice*2+dis);		}	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110408819 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！