「国家集训队」跳跳棋

发表于 | 分类于 | | 浏览量： 次

这题藏得有点深啊。

传送门

洛谷P1852

BZOJ2144

题解

这题的建模有点神仙。

根据题意，设三颗棋子的位置分别为$a,b,c(a<b<c)​$，令$d1=b-a,d2=c-b​$。

由题意可知，一共有三种移动方式：

  1. 中间的棋子往左跳。
  2. 中间的棋子往右跳。
  3. 两边的棋子中离中间棋子近的一颗往中间跳。

假如不断使用第三种跳法，那么对于任意一个状态，最后它将会跳到一个$d1=d2$的状态，此时便不能继续跳了。

并且对于任意一个状态，它只可能由两种状态执行操作三而转移过来。

所以如果以一个$d1=d2​$的状态作为根，每个状态向可能转移到该状态的两个状态建边，那么这将会是一颗二叉树。

对于两个状态，它们所对应的节点在树上的最短路径的长度就是转移所需的最小步数。

如果这两个状态不在同一棵树上，那么它们之间就不可能相互转移。

于是乎建出树之后，直接求LCA就行了。

但是还有一个问题就是树太大了，存不下。

那就可以先求出两个状态到根的深度，然后先把深度大的向上跳到深度相同，接着二分到LCA的距离即可。

注意当$d1$和$d2​$相差了好多倍时，可以一次性跳好几步，以免TLE。

然后就，没了…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<algorithm>
using namespace std;
int dep1,dep2,ans;
struct Ball
{
	int a,b,c;
	inline void Sort()
	{
		if(a>b) swap(a,b);
		if(a>c) swap(a,c);
		if(b>c) swap(b,c);
	}
	bool operator == (const Ball& b)const{return a==b.a&&this->b==b.b&&c==b.c;}
}A,B,tep1,tep2;
int GetFather(Ball x,int stp,Ball& lst)
{
	int d1=x.b-x.a,d2=x.c-x.b,ret=0;
	while(d1!=d2&&stp>0)
	{
		if(d1<d2)
		{
			if(d2%d1==0)
			{
				int nt=min(stp,d2/d1-1);
				x.a+=nt*d1;x.b+=nt*d1;
				stp=0;ret+=nt;
			}
			else
			{
				int nt=min(stp,d2/d1);
				x.a+=nt*d1;x.b+=nt*d1;
				stp-=nt;ret+=nt;
			}
		}
		else
		{
			if(d1%d2==0)
			{
				int nt=min(stp,d1/d2-1);
				x.b-=nt*d2;x.c-=nt*d2;
				stp=0;ret+=nt;
			}
			else
			{
				int nt=min(stp,d1/d2);
				x.b-=nt*d2;x.c-=nt*d2;
				stp-=nt;ret+=nt;
			}
		}
		d1=x.b-x.a;d2=x.c-x.b;
	}
	lst=x;
	return ret;
}
int main()
{
	scanf("%d%d%d%d%d%d",&A.a,&A.b,&A.c,&B.a,&B.b,&B.c);
	A.Sort();B.Sort();
	dep1=GetFather(A,2147483647,tep1);
	dep2=GetFather(B,2147483647,tep2);
	if(!(tep1==tep2))
	{
		printf("NO\n");
		return 0;
	}
	if(dep1>dep2)
	{
		ans+=dep1-dep2;
		GetFather(A,dep1-dep2,tep1);
		A=tep1;dep1=dep2;
	}
	if(dep2>dep1)
	{
		ans+=dep2-dep1;
		GetFather(B,dep2-dep1,tep2);
		B=tep2;dep2=dep1;
	}
	int L=0,R=dep1,mid;
	while(L<=R)
	{
		mid=(L+R)>>1;
		GetFather(A,mid,tep1);
		GetFather(B,mid,tep2);
		tep1==tep2?R=mid-1:L=mid+1;
	}
	ans+=L*2;
	printf("YES\n%d\n",ans);
	return 0;
}