不一样的LCA——luoguP1852跳跳棋
文章目录
在一条数轴上进行跳跳棋游戏。棋子只能摆在整点上。每个点不能摆超过一个棋子。用跳跳棋完成:棋盘上有3颗棋子,分别在a,b,c这三个位置。我们要通过最少的跳动把他们的位置移动成x,y,z。
跳动的规则:任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。如果可以完成输出YES以及所需步数,如果不行输出NO即可。
对,只允许跳过一颗棋子(因为这个想了好久自闭了)
看完题目之后第一反应是不是:woc这什么,跟LCA有什么关系??这哪来的树??
那就对了(%dalao)
分类讨论,发现对于每一种合法的状态(也就是没有棋子重合)只有三种情况能走
1.中点(y)向左边跳
2.中点(y)向右边跳
3.左边(或者右边)往中间跳 =>可以证明由于只能跳过一颗棋子,在d1!=d2时只能走一个
这好像有点像二叉树?(将1.2看做子节点,3看做父亲节点)
对于1.2情况,我们可以发现(以下以1为例):



可以知道,d1>d2时左边的棋子不能跳了,我们最多走d2/d1步,此时d2小于d1了换个方向走,当d2%d1等于0时走d2/d1-1步就到根了。
所以根据这个,我们可以求出开始状态与结束状态的祖先,判断他们的祖先是否相等 =>因为祖先相同就可以通过相反操作得到
这个操作模拟一下就好了,我们可以用除来加快跳((一个个跳会超时的)
模拟部分:
View Code
找到了公共祖先之后就可以二分查找(查找往上跳的步数)
l是0,r是min(结果与公共祖先的距离,起点与公共祖先的距离)
View Code
以上是我认为的核心内容(看不懂就感性理解一下)
[url=]
[/url]
1#include<iostream> 2#include<cstdio> 3usingnamespacestd; 4structnode{ 5 intx,y,z; 6}st,ed,b1,b2; 7intdep1,dep2; 8inlineintread(){ 9 charch;10 intsign=1;11 while((ch=getchar())<'0'||ch>'9')12 if(ch=='-') sign=-1;13 intres=ch-'0';14 while((ch=getchar())>='0'&&ch<='9')15 res=res*10+ch-'0';16 returnres*sign;17}18inlinevoidsort(node &x){19 if(x.x>x.y) swap(x.x,x.y);20 if(x.x>x.z) swap(x.x,x.z);21 if(x.y>x.z) swap(x.y,x.z);22}23inlineintfindfather(node &b){24 intres=0;25 sort(b);26 while(b.x+b.z!=b.y*2)27 {28 intd1=b.y-b.x;29 intd2=b.z-b.y;30 if(d1<d2)31 {32 intstep=d2/d1;33 if(d2%d1==0) step--;34 b.x+=step*d1;35 b.y+=step*d1;36 if(b.x>b.y) swap(b.x,b.y);37 res+=step;38 }39 else40 {41 intstep=d1/d2;42 if(d1%d2==0) step--;43 b.z-=step*d2;44 b.y-=step*d2;45 if(b.y>b.z) swap(b.y,b.z);46 res+=step;47 }48 }49 returnres;50}51inlineboolpd(node x,node y){52 if(x.x==y.x&&x.y==y.y&&x.z==y.z) returntrue;53 returnfalse;54}55inlineintabs(intx){56 returnx>=0?x:-x;57}58inline node go(node b,intdis){59 sort(b);60 while(dis)61 {62 intd1=b.y-b.x;63 intd2=b.z-b.y;64 if(d1<d2)65 {66 intstep=d2/d1;67 if(d2%d1==0) step--;68 if(step>dis) step=dis;69 b.x+=step*d1;70 b.y+=step*d1;71 if(b.x>b.y) swap(b.x,b.y);72 dis-=step;73 }74 else75 {76 intstep=d1/d2;77 if(d1%d2==0) step--;78 if(step>dis) step=dis;79 b.z-=d2*step;80 b.y-=d2*step;81 if(b.z<b.y) swap(b.z,b.y);82 dis-=step;83 }84 }85 returnb;86}87intmain(){88 st.x=read();st.y=read();st.z=read();89 ed.x=read();ed.y=read();ed.z=read();90 sort(st);sort(ed);91 b1=st;b2=ed;92 dep1=findfather(b1);93 dep2=findfather(b2);94 if(!pd(b1,b2))95 {96 printf("NO\n");97 return0;98 }99 else100 {101 intc=abs(dep1-dep2);102 if(dep1<dep2)103 ed=go(ed,c);104 elseif(dep1>dep2)105 st=go(st,c);106 intl=0,r=min(dep1,dep2),step=0;107 while(l<=r)108 {109 intmid=l+r>>1;110 b1=go(st,mid);111 b2=go(ed,mid);112 if(pd(b1,b2)) step=mid,r=mid-1;113 else l=mid+1;114 }115 printf("YES\n");116 printf("%d",step*2+c);117 }118 return0;119}[url=]
[/url]
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论