「BZOJ2144」跳跳棋

个人评价

挺好的一道题，难点在于想到树这个结构和建树

1 题面

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有 3 颗棋子，分别在 a,b,c 这三个位置。我们要通过最少的跳动把他们的位置移动成 x,y,z 。（棋子是没有区别的）跳动的规则很简单，任意选两颗棋子，选择两颗中一颗以另一颗为轴跳动。跳动后两颗棋子距离不变。一次只允许跳过 1 颗棋子。

这一坨还好，简单说：

总共给出6个点，前三个为初始点，后三个为目标点，有一个操作，可以将一个点为中轴，然后另外任意两个点选一个来跳，问至少跳几次就可以从3个初始节点到目标节点

2 分析题面

第一眼看，这个题跟树有毛个关系啊

第一时间想到的暴力肯定是dfs乱跑一通，但是绝对会炸掉，因为好像没有什么优秀的限制条件

我们手动算一下，每次有(3 * 2)=6次操作,也就是说每个点会有6种变化，有一点点恐怖

但是我们看一下，有几次实际上是在将这个三个点的包括范围扩大，所以对于答案没有影响（显然吧）

那么我们是不是就可把没用的状态删掉，那么就可以得到小小的优化

我们把推的状态和初始点建成一颗树，那是不是就感觉来了？

接下来仔细来分析下下

2.1大致分析和小小尝试

根据给的三个点a,b,c,我们维护一个递增三元组\((a,b,c)\)a<b<c

每次跳跃分三种情况:

b向c方向跳(点为\(2c-b\),三元组化为\((a,c,2c-b)\))
b向a方向跳(点为\(2a-b\),三元组化为\((2a-c,a,c)\))
两边往中间跳：

1.当\(b-a\)<\(c-b\)时\(a\)往\(b\)方向跳(点为\(2b-a\)，三元组化为(\(b,2b-a,c\)))

2.当\(b-a\)>\(c-b\)时\(c\)往\(b\)方向跳(点为\(2b-c\)，三元组化为(\(a,2b-c,b\)))

那肯定有人要问不是还有其他情况吗，但是你手动算一下，你的其他情况相当于是吧范围进行扩大，对最后答案的寻找没有影响，反而增加了状态的转移，使得计算变得复杂，所以舍掉

我们接下来就可以得到一个四叉树!？

我们无法确定这颗树到底有多大~~好像无限大的说~~，这4个状态只有两边往中间跳有限制（题目要求不能两个点在同一个位置，即d1!=d2）

那这个题不就无解了~~还不如打表加暴力~~？接下来进行一些神奇操作

2.2优化和正解

2.2.1 优化建树

观察是不是有在4种情况中，有两组两个的三元组有一个共同的没变化的点

我们把有共同无变化的点的三元组放在一起，这样4个状态就变成了2个

具体操作如下：

设\(d1=b-a,d2=c-b\)

讨论\(d1>d2\)的情况（d1<d2 同理）也就是考虑\(c\)往\(b\)的方向跳

c要跳到\(a\)与\(b\)之间也就是说设变换后的点\(c\)为\(c1\)其中a< c1 <b

每次跳跃距离为\(d2\)，跳跃总距离为\(d1-1\)那么次数为\((d1-1)/d2\)

设跳跃次数为t，那么多元组化为\((a,b-t*d2,c-t*d2)\)

每次有一个限制条件就是当d1=d2时就不行了

树大概长这个样子：

每次对于期望和起点，只要最后不是在同一颗树，也就是在dfs的结尾中，值（叶子节点）不一样，就无解

到这里我们就建完2颗二叉树了~~恭喜你到现在得到了10分~~

2.2.2使用lca

接下来就是这个题目的另一个难点——如何使用lca

我们观察两颗树，肯定有一个树是令一颗深度（即操作次数）的子树~~废话，都在同一颗树里面了~~

举个例子（例子中目标节点生成的树为子树，初始节点为父亲树）

我们要从初始节点到目标节点同一深度才可以找lca对吧

我们从初始节点进行t=A.times-B.times(A.times为初始节点到叶子节点的操作次数，B.times同理)

要是运气好，进行t次操作就得到目标节点了，ans=t

要是运气太拉了，到了目标节点的兄弟节点，我们就要lca了

但是我们怎么找这个lca呢？看之前的优化公式，我们是不是可以根据这个优化公式倒着上去找lca呢

那就可以二分答案这个上去的次数

2.2.3二分答案

二分答案从当前节点到lca节点需要的操作次数cnt，跟那个dfs长得差不多，具体操作见代码，

最后答案是A.times-B.times+2*cnt

3 代码实现（注释）

3.1定义

搞个结构体

struct G{
	int x,y,z,times;//x，y，z为递增三元组，times表示从操作前的根节点到叶子节点需要操作的次数
}A,B;

3.2 输入

先存入一个数组，然后排序，满足递增三元组要求

int a,b,c,x,y,z;
for(int i=1;i<=3;i++)scanf("%d",&t1[i]);
for(int i=1;i<=3;i++)scanf("%d",&t2[i]);
sort(t1+1,t1+4);
sort(t2+1,t2+4);
a=t1[1],b=t1[2],c=t1[3];
x=t2[1],y=t2[2],z=t2[3];

3.3 计算

1.先dfs跑出两个二叉树~~其实不是树，只是树对于想题来说好一点~~

2.判断是不是在同一颗二叉树里面

3.从父亲树的根节点跑到跟子树同深度

4.二分答案

3.4 输出

A.times-B.times+cnt*2

3.5 总体代码

带上注释

#include<bits/stdc++.h>
using namespace std;
int t1[5],t2[5];
struct G{
	int x,y,z,times;
}A,B;
int dfs(int a1,int b1,int c1,int k){//k是用来判断是初始节点建的树还是目标节点
	int cnt=0;
	while(1){
		int d1=b1-a1,d2=c1-b1;
		if(d1==d2)break;
		if(d1>d2){//分析的优化
			int t=(d1-1)/d2;//减一是为了防止两个点跳一起了
			cnt+=t,b1-=t*d2,c1-=t*d2;//推导的公式
		}else{
			int t=(d2-1)/d1;//同理
			cnt+=t,a1=a1+t*d1,b1=b1+t*d1;//d1<d2与上面同理
		}
	}
	if(k){//将两个树的叶子节点存着，方便判断
		A.x=a1,A.y=b1,A.z=c1,A.times=cnt;
	}else{
		B.x=a1,B.y=b1,B.z=c1,B.times=cnt;
	}
}
bool check(int t,int a,int b,int c,int x,int y,int z){//二分
	int tot=t;
    //这里的操作和dfs是差不多的
	while(tot){//开始找lca了
		int d1=b-a,d2=c-b;
		if(d1==d2)break;
		if(d1>d2){
			int t=min((d1-1)/d2,tot);//min和max都是为了防止炸掉
			tot=max(0,tot-t),b-=t*d2,c-=t*d2;
		}else{
			int t=min(tot,(d2-1)/d1);
			tot=max(tot-t,0),a=a+t*d1,b=b+t*d1;
		}
	}
	tot=t;
	while(tot){//跟上面同理
		int d1=y-x,d2=z-y;
		if(d1==d2)break;
		if(d1>d2){
			int t=min((d1-1)/d2,tot);
			tot=max(tot-t,0),y-=t*d2,z-=t*d2;
		}else{
			int t=min((d2-1)/d1,tot);
			tot=max(tot-t,0),x=x+t*d1,y=y+t*d1;
		}
	}
	if(a==x&&y==b&&z==c)return 1;//是不是满足条件
	else return 0;
}
int main(){
	int a,b,c,x,y,z;
	for(int i=1;i<=3;i++)scanf("%d",&t1[i]);
	for(int i=1;i<=3;i++)scanf("%d",&t2[i]);
	sort(t1+1,t1+4);//构造递增三元组
	sort(t2+1,t2+4);//排序
	a=t1[1],b=t1[2],c=t1[3];
	x=t2[1],y=t2[2],z=t2[3];
	dfs(a,b,c,1),dfs(x,y,z,0);
	if(A.x!=B.x||A.y!=B.y||A.z!=B.z){//判断是不是在同一颗树里面
		printf("NO");
		return 0;
	}else{
		printf("YES\n");
	}
	if(A.times<B.times){//让A里面放父亲树的值
		swap(a,x),swap(b,y),swap(c,z); 
		swap(A.times,B.times);
	}
	int tot=A.times-B.times;
	while(tot){//跑到同一深度
		int d1=b-a,d2=c-b;
		if(d1==d2)break;
		if(d1>d2){
			int t=min((d1-1)/d2,tot);
			tot-=t,b-=t*d2,c-=t*d2;
		}else{
			int t=min((d2-1)/d1,tot);
			tot-=t,a=a+t*d1,b=b+t*d1;
		}
	}
	int l=0,r=max(A.times,B.times),cnt1=0;
	while(l<=r){//开始二分
		int mid=(l+r)>>1;
		if(check(mid,a,b,c,x,y,z)){
			r=mid-1;
			cnt1=mid;
		}else{
			l=mid+1;
		}
	}
	printf("%d",cnt1*2+A.times-B.times);
}