【国家集训队】跳跳棋

Source and Judge

bzoj2144
luogu1852

Record

2h

Analysis

请先思考后再展开

很好的题目
不妨设a<b<c

考虑我能怎么跳
因为题目要求,每次只能跳过一个棋子
发现在任意时刻,只有三种移动方法
$dis1=b-a,dis2=c-b$

  1. $a-dis1,a,c$
  2. $a,c,c+dis2$
  3. $b,b+dis1,c$ 或者 $a,b-dis2,b$ (如果都不行,则没有)
    度大部分都是3,你想到了什么?
    一棵二叉树!
    把第一种和第二种,看作是孩子,第三种看作是父亲
    不过,树的深度无限,因为你总是能不停向外跳的

那么我们来证明一下这为什么是一棵二叉树(网上的漏点)

  1. 对于没有父亲的节点,本身就是根节点,所以严格来说这是一个二叉树森林
  2. 我们必须要证明x的祖先不可能会出现在x的子树中
    如果我们定义一个值:最接近两点间的距离
    不难发现,向上时必定变小,向下时必定变大(不能够重叠棋子)
  3. 操作可逆,所以是无向图

那么,现在要求的就是两个节点间的lca
此时已经有40分了,如何避免暴力存图呢?

考虑每次向上跳(再也不用考虑向下了,我向下就是等它上来)
如果方向是相同的(缩左边或者缩右边),那么间距不变,
可以直接通过一个除法来计算出来,然后距离取模
那么复杂度基本上就是log(参考gcd的复杂度)
如果要限制长度,可以判断一下,确保不超过(当覆盖时)

那么找lca的时候,先到相同高度,然后二分向上距离即可

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
int a,b,c;
Nod(int x=0,int y=0,int z=0) {a=x,b=y,c=z;}
};
int dep;
Nod jump(Nod now,int mx)//限制步数
{
int a=now.a,b=now.b,c=now.c;
dep=0;
while(1)
{
int stp=0;
int dis1=b-a,dis2=c-b;
if(dis1<dis2)
{
stp=mymin(mx-dep,(dis2-1)/dis1);
a+=stp*dis1,b+=stp*dis1;
}
else if(dis2<dis1)
{
stp=mymin(mx-dep,(dis1-1)/dis2);
b-=stp*dis2,c-=stp*dis2;
}
dep+=stp;
if(stp==0) return Nod(a,b,c);
}
}
bool check(Nod x,Nod y,int mx)
{
x=jump(x,mx);y=jump(y,mx);
return x.a==y.a and x.b==y.b and x.c==y.c;
}
Nod ss(Nod now)
{
if(now.a>now.b) swap(now.a,now.b);
if(now.a>now.c) swap(now.a,now.c);
if(now.b>now.c) swap(now.b,now.c);
return now;
}
void main()
{
Nod x,y;scanf("%d%d%d%d%d%d",&x.a,&x.b,&x.c,&y.a,&y.b,&y.c);
x=ss(x);y=ss(y);//debug 漏了
jump(x,2*INF);int xdep=dep;
jump(y,2*INF);int ydep=dep;
if(xdep<ydep) swap(xdep,ydep),swap(x,y);
x=jump(x,xdep-ydep);
int l=0,r=ydep,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(x,y,mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans<0) puts("NO");
else printf("YES\n%d",2*ans+xdep-ydep);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/4147.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%