bzoj2144: 跳跳棋(二分/倍增)

时间:2021-04-14 23:23:43

  思维好题!

  可以发现如果中间的点要跳到两边有两种情况,两边的点要跳到中间最多只有一种情况。

  我们用一个节点表示一种状态,那么两边跳到中间的状态就是当前点的父亲,中间的点跳到两边的状态就是这个点的两个儿子,从而组成一棵二叉树。

  于是两个状态能够达到当且仅当他们在同一棵树上,只要看看根节点是否一样就好了。

  那怎么求两个状态的最短距离呢?我们考虑两边的点跳到中间实际上是一个更相相损的过程,于是我们像gcd一样做就可以优化成log级别的了。求两个状态的最短距离实际上就是求两个节点在树上的距离,像倍增求lca一样,先跳到一样的高度,然后二分一下高度,找到LCA算就好了。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
struct poi{int x,y,z;}a,b,x,y;
int high,len,lena,lenb;
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
poi climb(poi now,int time)
{
for(len=;time;len+=high)
{
int l=now.y-now.x,r=now.z-now.y;
if(l==r)return now;
if(l<r)high=min((r-)/l,time),time-=high,now.x+=l*high,now.y+=l*high;
else high=min((l-)/r,time),time-=high,now.y-=r*high,now.z-=r*high;
}
return now;
}
void sort(poi &now)
{
if(now.x>now.y)swap(now.x,now.y);
if(now.x>now.z)swap(now.x,now.z);
if(now.y>now.z)swap(now.y,now.z);
}
int main()
{
read(a.x);read(a.y);read(a.z);
read(b.x);read(b.y);read(b.z);
sort(a);sort(b);
x=climb(a,inf);lena=len;
y=climb(b,inf);lenb=len;
if(x.x!=y.x||x.y!=y.y||x.z!=y.z)return puts("NO"),;
puts("YES");
if(lena<lenb)swap(a,b),swap(lena,lenb);
a=climb(a,lena-lenb);
int l=,r=lenb;
while(l<r)
{
int mid=(l+r)>>;
x=climb(a,mid);y=climb(b,mid);
if(x.x==y.x&&x.y==y.y&&x.z==y.z)r=mid;
else l=mid+;
}
printf("%d",(l<<)+lena-lenb);
}