首页 > 代码库 > BZOJ 2144 跳跳棋
BZOJ 2144 跳跳棋
2144: 跳跳棋
Description
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。 写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
Input
第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）第二行包含三个整数，表示目标位置x y z。（互不相同）
Output
如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。
Sample Input
1 2 3
0 3 5
0 3 5
Sample Output
YES
2
【范围】
100% 绝对值不超过10^9
2
【范围】
100% 绝对值不超过10^9
啊啊啊。曾祥瑞学长说，这是一道思考题。于是，我们都误以为这是一道数论题。后来才发现，自己实在是太NAIVE了。
hzwer说：
这道题广搜20分。
但是，对于一个状态，例如2 3 7
中间可以往两侧跳，即2 3 7->1 2 7 / 2 3 7->2 7 11
两侧仅有一个能往中间跳，即2 3 7->3 4 7
那么所有的状态就能表示为一棵二叉树，第一种情况为其两个儿子，第二种为其父亲
问题转换为给定树上的两个结点，求其距离
直接暴力可以得40分
可以构造这样的数据
1 2 1000000000
99999998 99999999 1000000000
这样左边要一直往中间跳上上亿次
我们发现若记前两个数差t1，后两个数差t2，不妨设t1<t2
则左边最多往中间跳(t2-1)/t1次
然后只能右边往中间跳，是一个辗转相除的过程，即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点，或者根节点，同时还可以顺便算下深度
那么只要求始终两个状态的深度d1,d2,将较深的调整到同一深度
然后二分/倍增求与lca的深度差x
ans=2*x+abs(d1-d2)
啊啊啊啊啊。实在不想多说了，二分O（log n）* 辗转相除O(log n)，实在是太优了。现在仔细想来，这确实是一道思维题，很重要的是，末状态就是二者等距。这个模型确实很有实际意义。
1 /************************************************************** 2 Problem: 2144 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:820 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 struct data {int pos[4];}a,b;13 int dep=0;14 bool operator!=(data a,data b) {for( int i = 1; i <= 3; i++ ) if(a.pos[i]!=b.pos[i]) return 1;return 0;}15 data cal(data x,int heig) {16 while(heig) {17 int d1=x.pos[2]-x.pos[1], d2=x.pos[3]-x.pos[2];18 if(d1==d2) return x;19 if(d1<d2) {20 int t=std::min(heig,(d2-1)/d1);21 heig-=t;dep+=t;22 x.pos[1]+=t*d1;x.pos[2]+=t*d1;23 } else {24 int t=std::min(heig,(d1-1)/d2);25 heig-=t;dep+=t;26 x.pos[2]-=t*d2;x.pos[3]-=t*d2;27 }28 }29 return x;30 }31 int main() {32 for( int i = 1; i <= 3; i++ ) scanf("%d",&a.pos[i]);33 for( int i = 1; i <= 3; i++ ) scanf("%d",&b.pos[i]);34 std::sort(a.pos+1,a.pos+4);std::sort(b.pos+1,b.pos+4);35 data t1=cal(a,0x3f3f3f3f);int d1=dep;dep=0;36 data t2=cal(b,0x3f3f3f3f);int d2=dep;dep=0;37 if(t1!=t2) printf("NO\n"), std::exit(0);38 if(d1<d2) std::swap(d1,d2), std::swap(a,b);39 int ans=d1-d2;a=cal(a,ans);40 int lf=0, rg=d2;41 while(lf<=rg) {42 int mid=(lf+rg)>>1;43 if(cal(a,mid)!=cal(b,mid)) lf=mid+1;44 else rg=mid-1;45 }46 printf("YES\n%d\n",ans+2*lf);47 return 0;48 }49
BZOJ 2144 跳跳棋
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。