BZOJ2144: 跳跳棋

神题一道。

考虑题目性质。首先对于一个状态，只存在四种情况，即最左/右边的点跳到中间，中间的点跳到左/右。而对于一个状态，显然第一种情况的两种分支不能同时存在，那么题目就可以理解为从$(a,b,c)$找到一条最短的路径可以使得其到达$(x,y,z)$，你完全可以把所有状态存下来随便跑个最短路算法，但是显然是无法承受的，而再研究题目可以发现如果根据一个状态的情况连边，所形成的图是一棵树，而且还是个二叉树，那么就可以利用这个性质。那么假设现在一个状态是$(x,y,z)$，设$t1=y-x,t2=z-y$。如果$t1==t2$，那么就代表这个节点是个根节点。为了简化题目，不考虑每个节点的儿子情况，只考虑他的父亲，那么这个题目就可以看作在一棵树里找两个点的LCA。那么如何求一个节点的第$k$个祖先？

根据gcd的一些奇奇怪怪的性质，可以发现如果$t1>t2$，那么不断将最左边的点移到中间，最多可以移$\frac{t1-1}{t2}$，根据这个也很容易算出移动后的状态。

剩下的就很好搞了，倍增二分什么的都可以，我用的是二分。

//BZOJ 2144
//by Cydiater
//2016.10.20
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int dep1,dep2,ans=0;
struct Node{
	int x,y,z;
	void Sort(){if(x>y)swap(x,y);if(x>z)swap(x,z);if(y>z)swap(y,z);}
}a,b;
bool operator == (Node x,Node y){return x.x==y.x&&x.y==y.y&&x.z==y.z;}
namespace solution{
	void init(){
		a.x=read();a.y=read();a.z=read();
		b.x=read();b.y=read();b.z=read();
	}
	int get(Node node){
		int x=node.x,y=node.y,z=node.z;
		int t1=abs(y-x),t2=abs(z-y),Ans=0;
		while(t1!=t2&&t1*t2!=0){
			if(t1<t2)swap(t1,t2);
			Ans+=(t1-1)/t2;
			int tmp=t1;t1=t2;t2=tmp%t2;
		}
		return Ans;
	}
	Node jump(Node t,int dist){
		if(get(t)<dist)return (Node){oo,oo,oo};
		t.Sort();
		while(dist){
			if(t.y-t.x>t.z-t.y){
				int t1=t.y-t.x,t2=t.z-t.y;
				if((t1-1)/t2<dist){
					dist-=(t1-1)/t2;
					t.y-=(t1-1)/t2*t2;
					t.z-=(t1-1)/t2*t2;
				}else{
					t.y-=dist*t2;
					t.z-=dist*t2;
					dist=0;
				}
			}else{
				int t1=t.y-t.x,t2=t.z-t.y;
				if((t2-1)/t1<dist){
					dist-=(t2-1)/t1;
					t.x+=(t2-1)/t1*t1;
					t.y+=(t2-1)/t1*t1;
				}else{
					t.x+=dist*t1;
					t.y+=dist*t1;
					dist=0;
				}
			}
		}
		return t;
	}
	void slove(){
		if(a==b){puts("YES");puts("0");return;}
		a.Sort();b.Sort();
		dep1=get(a);dep2=get(b);
		if(dep1<dep2){swap(a,b);swap(dep1,dep2);}
		ans+=dep1-dep2;
		a=jump(a,dep1-dep2);
		if(a.x==oo){puts("NO");return;}
		if(a==b){puts("YES");cout<<ans<<endl;return;}
		int leftt=1,rightt=1000000000,mid;
		while(leftt+1<rightt){
			mid=(leftt+rightt)>>1;
			if(jump(a,mid)==jump(b,mid))rightt=mid;
			else                        leftt=mid;
		}
		if(jump(a,leftt)==jump(b,leftt)&&jump(a,leftt).x!=oo){
			puts("YES");
			printf("%d\n",ans+(leftt<<1));
		}
		else if(jump(a,rightt)==jump(b,rightt)&&jump(a,rightt).x!=oo){
			puts("YES");
			printf("%d\n",ans+(rightt<<1));
		}
		else puts("NO");
	}
}
int main(){
	//freopen("input.in","r",stdin);
	using namespace solution;
	init();
	slove();
	return 0;
}

巴特西

BZOJ2144: 跳跳棋

最新文章

热门文章