三向城(noip模拟题)

Posted by yjjr's blog on February 6, 2018

标签:树,LCA

题目描述

三向城是一个巨大的城市,之所以叫这个名字,是因为城市中遍布着数不尽的三岔路口。(来自取名力为0的出题人)

具体来说,城中有无穷多个路口,每个路口有唯一的一个正整数标号。除了1号路口外,每个路口都连出正好3条道路通向另外3个路口:编号为x(x>1)的路口连出3条道路通向编号为x*2,x*2+1和x/2(向下取整)的3个路口。1号路口只连出两条道路,分别连向2号和3号路口。

所有道路都是可以双向通行的,并且长度都为1。现在,有n个问题:从路口x到路口y的最短路长度是多少?

 

输入格式

       第一行包含一个整数n,表示询问数量;

       接下来n行,每行包含两个正整数x, y,表示询问从路口x到路口y的最短路长度。

 

输出格式

       输出n行,每行包含一个整数,表示对每次询问的回答。如果对于某个询问不存在从x到y的路径,则输出-1。

      

样例输入

3

5 7

2 4

1 1

 

样例输出

4

1

0

 

样例解释

       5号路口到7号路口的路径为:5->2->1->3->7,长度为4;

       2号路口到4号路口的路径为:2->4,长度为1;

       1号路口到本身的路径长度为0;

 

数据范围

       对30%的数据,x,y≤20;

       对60%的数据,x,y≤105,n≤10;

       对100%的数据,x,y≤109,n≤104

 

先吐槽下出题人yy题目的语言功底……

T1难度,用LCA思想直接做

 

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxx=31;
int n,depx,depy,ans=0;
ll x,y;

int Deep(ll x)
{
	rep(k,1,maxx)
	    if((ll)(1<<k)>x)return k;
}
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	n=read();
	rep(i,1,n){
		ans=0;
		x=read(),y=read();
		depx=Deep(x),depy=Deep(y);
		if(depx<depy){swap(x,y);swap(depx,depy);}
		dep(j,depx,depy+1){x/=2;ans++;}//cout<<ans<<"R\n";cout<<x<<' '<<depx<<endl;cout<<y<<' '<<depy<<endl;
		dep(j,depy,0){if(x==y)break;x/=2,y/=2;ans+=2;}
		printf("%d\n",ans);
	}
	return 0;
}
		



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr