【题解】P1852 跳跳棋

link

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。棋盘上有3颗棋子，分别在 \(a，b，c\) 这三个位置。我们要通过最少的跳动把他们的位置移动成 \(x，y，z\) 。（棋子是没有区别的）

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。

判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

思路

神仙题……非常巧妙地建模。只能说：女少口阿

首先，对于中轴棋子为 \(b\) （中间那个）的情况，显然一直往中间跳可以一直减小范围，直到不能跳为止。这时候就得到了一个非常有用的“Basic” 状态，也就是“根状态”（这怎么跟某道字符串手玩题这么像啊）

然后把 \(b\) 往左右跳的情况看成左右节点状态，那么所有状态构成了一棵二叉树。对于棋盘上所有的 \(a,b,c\) ，状态构成了一个森林。

那么，如果 \((a,b,c)\to (x,y,z)\) ，首要条件是在同一棵树上。这样第一问就解决了。

考虑状态怎么去树根。利用 LCA 的思想，把两个状态到根的距离调整到一样，然后二分向上的步数，最后找到一个 \(L\) 使得两个状态向上 \(L\) 步相遇，那么总答案就是 高度差加上二分答案的两倍。

代码

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9+7;

int sx,sy,sz,dep,mx;

void init( 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 );

}

void dfs( int x,int y,int z,int step )

{

	int del1=y-x,del2=z-y;

	if ( step==mx || del1==del2 ) { sx=x,sy=y,sz=z; dep=step; return; }

	if ( del1>del2 )

	{

		swap( del1,del2 ); int del=del2/del1;

		if ( del2%del1==0 ) del--;

		if ( step+del<=mx ) dfs( x,y-del*del1,z-del*del1,step+del );

		else dfs( x,y-(mx-step)*del1,z-(mx-step)*del1,mx );

	}

	else

	{

		int del=del2/del1;  del-=(del2%del1==0);

		if ( step+del<=mx ) dfs( x+del*del1,y+del*del1,z,step+del );

		else dfs( x+(mx-step)*del1,y+(mx-step)*del1,z,mx );

	}

}

int main()

{

	int x,y,z,a,b,c;

	scanf( "%d%d%d",&a,&b,&c ); init( a,b,c );

	scanf( "%d%d%d",&x,&y,&z ); init( x,y,z );

	mx=inf;

	dfs( a,b,c,0 ); int sa=sx,sb=sy,sc=sz,sd=dep;

	dfs( x,y,z,0 );

	if ( sx!=sa || sy!=sb || sz!=sc ) { printf( "NO" ); return 0; }

	printf( "YES\n" );

//------------query1-------------------

	int ans=0;

	if ( sd>dep )

	{

		ans=sd-dep; mx=sd-dep;

		dfs( a,b,c,0 ); a=sx; b=sy; c=sz;

	}

	if ( sd<dep )

	{

		ans=dep-sd; mx=dep-sd;

		dfs( x,y,z,0 ); x=sx,y=sy,z=sz;

	}

	int l=0,r=inf;

	while ( l<=r )

	{

		mx=(l+r)>>1;

		dfs( a,b,c,0 ); sa=sx,sb=sy,sc=sz;

		dfs( x,y,z,0 );

		if ( sa!=sx || sb!=sy || sc!=sz ) l=mx+1;

		else r=mx-1;

	}

	printf( "%d",(l<<1)+ans );

}