跳跳棋「LCA+二分答案」

题目描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在\(a，b，c\)这三个位置。我们要通过最少的跳动把他们的位置移动成\(x，y，z\)。（棋子是没有区别的）

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

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

输入格式

第一行包含三个整数，表示当前棋子的位置\(a\) \(b\) \(c\)。（互不相同）

第二行包含三个整数，表示目标位置\(x\) \(y\) \(z\)。（互不相同）

输出格式

如果无解，输出一行\(NO\)。

如果可以到达，第一行输出\(YES\)，第二行输出最少步数。

输入输出样例

输入 #1

1 2 3
0 3 5

输出 #1

YES
2

说明/提示

\(20%\) 输入整数的绝对值均不超过\(10\)

\(40%\) 输入整数的绝对值均不超过\(10000\)

\(100%\) 绝对值不超过\(10^{9}\)

---

思路分析

声明：本蒟蒻喜欢把东西讲的很详细（因为我不会），所以篇幅有点长

此题神级建模！
——老姚

没有思路

神级建模，暗示看不出来

清华集训，暗示本蒟蒻不配

这题是真滴没想到能扯到\(LCA\)果断一个特判一个NO骗分就走

• 这题只有三个棋子，棋子的移动还算比较单一，尽管可以构成数不清的情况，以这个作为一个突破点

• 假设三颗棋子的初始位置是\(x,y,z\),棋子的移动情况大体上一共就两种：

  1. 两端向中间跳
  2. 中间向两端跳

• 不难发现，对于第\(2\)种情况，棋子的跳动是没有限制的，想跳多远就能跳多远，关键在于第1种情况

• 针对第\(1\)种情况，我们设\(x\)到\(y\)的距离为\(d_{1}\)，\(y\)到\(z\)的距离为\(d_{2}\)，此时可以再划分出三种小情况（注意都是向中间）：

  1. \(d_{1}\)>\(d_{2}\)：这时候只能\(z\)跳到\(x\)，\(y\)的中间，等价于\(y\)和\(z\)向左平移\(d_{2}\)个单位长度（注意这里的\(xyz\)是三个棋子的相对顺序，而不是编号）
  2. \(d_{1}<d_{2}\)：与上述情况相似，\(x\)跳，等价于\(x\)和\(y\)向右平移\(d_{1}\)个单位长度
  3. \(d_{1}==d_{2}\)：划~重~点~。不难发现，此时两边的棋子已经无法再向中间跳了，我们将其成为终极状态，再次找到突破点

• 以这个终极状态为出发点，通过棋子的花式跳动可以跳出许多状态，我们称其为子状态。显而易见的一个性质就是，这个终极状态的任意两个子状态，都可以通过先转化为终极状态，再互相到达彼此的状态

• 由此，有没有联想到什么？？是不是和树很像？终极状态就是根节点，而子状态就是这个树上的任意一个节点。那么对于两种棋子的状态是否能互相转化，我们只需要判断其跟节点，即终极状态是否相同即可,只不过每个节点是三个点的坐标的结构体。

• 那最小步数到这里应该也比较明了了，和判断是否能互相转化的思想类似，只不过不需要跳到终极状态而已，但肯定需要一个相同的中间状态来转化，而且还需要步数最小，那不就是最近公共祖先（LCA）吗？

• 剩下最后一个问题，数据范围这么大你总不能建一棵树出来吧？那要怎么收敛状态？考虑转移过程，对于像\(1,2，1e9\)这种数据，我们其实可以一下处理出跳的次数的，在这种情况下，每一次跳的距离是一样的，所以我们可以求出连续跳 \(k=(d_{2}−1)/d_{1}\) 次后 \(d_{1}>=d_{2}\)（记得-1，否则可能重合）

• 那么公共祖先就可以在这个数轴上二分枚举了，这道题基本解决

---

细节见代码

Code

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read(){
	int x = 0,f = 1;
	char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x = (x<<1)+(x<<3)+(ch^48);ch = getchar();}
	return x*f;
}
const int inf = 0x3f3f3f3f;
struct Node{
	int x,y,z;
	void Init(){
		x = read(),y = read(),z = read();
		if(x>y)swap(x,y); //记得维护顺序
		if(x>z)swap(x,z);
		if(y>z)swap(y,z);
	}
}a,b,ra,rb;
bool check(Node u,Node v){ //判断终极状态相同与否
	return u.x==v.x&&u.y==v.y&&u.z==v.z;
}
int step,k;
Node getroot(Node t,int s){ //转移到终极状态
	for(step=0;s;step+=k){
		int d1 = t.y-t.x,d2 = t.z-t.y;
		if(d1==d2)return t;
		if(d1<d2){
			k = min((d2-1)/d1,s); //跳多些
			t.x+=k*d1,t.y+=k*d1;
			s-=k;
		}
		else{
			k = min((d1-1)/d2,s);
			t.z -= k*d2,t.y-=k*d2;
			s-=k;
		}
	}
	return t;
}
int main(){
	a.Init(),b.Init();
	ra = getroot(a,inf);
	int step1 = step;
	rb = getroot(b,inf);
	int step2 = step;
	if(!check(ra,rb)){ //不同
		printf("NO\n");
		return 0;
	}
	if(step1<step2){ //一般求LCA的思想，先让远的先跳
		swap(a,b);
		swap(step1,step2);	
	}
	a = getroot(a,step1-step2);//跳到相同位置再一起跳
	int l = 0,r = step2;
	while(l<r){
		int mid = (l+r)>>1; //枚举到祖先的距离，一起跳
		if(check(getroot(a,mid),getroot(b,mid)))r = mid;
		else l = mid+1;
	}
	printf("YES\n%d\n",(l<<1)+step1-step2);//记得×2和加上a先跳的
}