2144: 跳跳棋
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 492 Solved: 244
[Submit][Status][Discuss]
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
2
【题解】
一道关于lca+二分+模拟gcd的神题，蒟蒻不得不偷窥了题解
在序列上一共有2种操作：
中间可以往两侧跳
两侧仅有一个能往中间跳
那么所有的状态就能表示为一棵二叉树，第一种情况为其两个儿子，第二种为其父亲
问题转换为给定树上的两个结点，求其距离
我们发现若记前两个数差t1，后两个数差t2，不妨设t1<t2
则左边最多往中间跳(t2-1)/t1次
然后只能右边往中间跳，是一个辗转相除的过程，即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点，或者根节点，同时还可以顺便算下深度
那么只要求始终两个状态的深度d1,d2,将较深的调整到同一深度
然后二分/倍增求与lca的深度差x
ans=2*x+abs(d1-d2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define INF 1000000000
struct node{int v[];}root1,root2;
int temp,temp1,temp2,ans,a[],b[];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
node dfs(int p[],int k)
{
node ans;
for(int i=;i<=;i++) ans.v[i]=p[i];
int t1=p[]-p[],t2=p[]-p[];
if(t1==t2) return ans;
if(t1<t2)
{
int step=min(k,(t2-)/t1);
k-=step; temp+=step;
ans.v[]+=step*t1; ans.v[]+=step*t1;
}
if(t1>t2)
{
int step=min(k,(t1-)/t2);
k-=step; temp+=step;
ans.v[]-=step*t2; ans.v[]-=step*t2;
}
if(k) return dfs(ans.v,k);
else return ans;
}
bool operator!=(node a,node b){for(int i=;i<=;i++)if(a.v[i]!=b.v[i])return ;return ;}
int main()
{
freopen("cin.in","r",stdin);
freopen("cout.out","w",stdout);
for(int i=;i<=;i++) a[i]=read();
for(int i=;i<=;i++) b[i]=read();
sort(a+,a+); sort(b+,b+);
root1=dfs(a,INF); temp1=temp; temp=;
root2=dfs(b,INF); temp2=temp; temp=;
if(root1!=root2) {printf("NO\n"); return ;}
if(temp1>temp2)
{
swap(temp1,temp2);
for(int i=;i<=;i++)swap(a[i],b[i]);
}
ans=temp2-temp1;
root1=dfs(b,ans);
for(int i=;i<=;i++)b[i]=root1.v[i];
int l=,r=temp1;
while(l+<r)
{
int mid=(l+r)/;
if(dfs(a,mid)!=dfs(b,mid)) l=mid;
else r=mid;
}
if(dfs(a,l)!=dfs(b,l)) temp=r;
else temp=l;
printf("YES\n%d\n",ans+*temp);
return ;
}