其实这道题并不是很难, 但是确实不太好想啊...
题目大意:
跳跳棋是在一条数轴上进行的. 棋子只能摆在整点上. 每个点不能摆超过一个棋子.
我们用跳跳棋来做一个简单的游戏: 棋盘上有 3 颗棋子, 分别在 a,b,c 这三个位置. 我们要通过最少的跳动把他们的位置移动成 x,y,z.(棋子是没有区别的)
跳动的规则很简单, 任意选一颗棋子, 对一颗中轴棋子跳动. 跳动后两颗棋子距离不变. 一次只允许跳过 1 颗棋子.
我们仔细的剖析一下题意:
我们从题目中可知, 一共只有三种移动方式:
1. 中间的棋子往左跳
2. 中间的棋子往右跳
3. 两边离中间近的棋子往中间跳 (因为如果是远的棋子的话就会跳过两个了...)
那么我们知道, 如果不断进行第三步操作, 最后一定会得到中间棋子到两边距离相等的情况, 那么如果两种摆放方式经过这种迭代后, 到中间距离相等, 那么就代表他们是可以互相转换的, 反之则不能.
那么我们就可以判断是否可以完成任务了, 而且我们知道棋子看的是相对位置, 那么 a b c, 将 a 跳到 bc 中间就等于 a,b 同时向右移 ab 的差值, 但是我们发现每一次减速度太慢, 所以我们大可以将每一次移动差值步改为移动另一个差值 % 这个差值步, 想一想正确性?
那么, 我们怎么计算需要多少步呢? 由于我们知道每一次都有三种选择, 那么如果我们从距离相等的情况开始拓展, 那么就会有两种选择. 也就是这些状态构成了一颗二叉树.
那么我们所求的答案就是树上两点间距离啦!
这个建一个树当然也可以, 或者直接判断也行...
关于时间复杂度, 由于取模运算和 gcd 比较类似, 所以忽略常数影响, 应该是 log 级别的: logx(x 是给出的最大距离差)
最后, 附上本题代码:
- #include<cstdio>
- #include<iostream>
- //Debug Yufenglin
- #define debugj printf("Running\n");
- #define debugp1(x) printf("%d\n",x);
- #define debugp2(x,y) printf("%d %d\n",x,y);
- #define debugp3(x,y,z) printf("%d %d %d\n",x,y,z);
- //Standfor Yufenglin
- #define LL long long
- #define LB long double
- #define reg register
- #define il inline
- #define inf 1e8
- #define maxn 1e5
- using namespace std;
- struct state
- {
- int x,y,z;
- };
- state pre,now,c1,c2,ct1,ct2;
- int abs(int x)
- {
- if(x<0) return -x;
- return x;
- }
- void merge(state &w)
- {
- if(w.x>w.y) swap(w.x,w.y);
- if(w.y>w.z) swap(w.y,w.z);
- if(w.x>w.y) swap(w.x,w.y);
- }
- bool judge(state a,state b)
- {
- if(a.x==b.x&&a.y==b.y&&a.z==b.z) return 1;
- return 0;
- }
- int find_father(state &w)
- {
- int step=0;
- while(w.x+w.z!=2*w.y)
- {
- int s1=w.y-w.x,s2=w.z-w.y;
- if(s1>s2)
- {
- int tep=s1/s2;
- if(s1%s2==0) tep--;
- w.y-=tep*s2;
- w.z-=tep*s2;
- merge(w);
- step+=tep;
- }
- else
- {
- int tep=s2/s1;
- if(s2%s1==0) tep--;
- w.x+=tep*s1;
- w.y+=tep*s1;
- merge(w);
- step+=tep;
- }
- }
- return step;
- }
- state update(state w,int mid)
- {
- merge(w);
- while(mid!=0)
- {
- int s1=w.y-w.x,s2=w.z-w.y;
- if(s1>s2)
- {
- int tep=s1/s2;
- if(s1%s2==0) tep--;
- tep=min(tep,mid);
- w.y-=tep*s2;
- w.z-=tep*s2;
- merge(w);
- mid-=tep;
- }
- else
- {
- int tep=s2/s1;
- if(s2%s1==0) tep--;
- tep=min(tep,mid);
- w.x+=tep*s1;
- w.y+=tep*s1;
- merge(w);
- mid-=tep;
- }
- }
- return w;
- }
- int main()
- {
- scanf("%d%d%d%d%d%d",&pre.x,&pre.y,&pre.z,&now.x,&now.y,&now.z);
- merge(pre),merge(now);
- c1=pre,c2=now;
- int temp1=find_father(pre),temp2=find_father(now);
- if(judge(pre,now)==0) printf("NO\n");
- else
- {
- int dt=abs(temp1-temp2),l=0,r=min(temp1,temp2),ans;
- if(temp1<temp2) c2=update(c2,dt);
- else c1=update(c1,dt);
- while(l<=r)
- {
- int mid=(l+r)>>1;
- ct1=update(c1,mid);
- ct2=update(c2,mid);
- if(judge(ct1,ct2)==1) ans=mid,r=mid-1;
- else l=mid+1;
- }
- printf("YES\n%d\n",dt+ans*2);
- }
- return 0;
- }
跳跳棋
来源: http://www.bubuko.com/infodetail-3005529.html