三向城
题目描述
三向城是一个巨大的城市，之所以叫这个名字，是因为城市中遍布着数不尽的三岔路口。（来自取名力为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。
思路：
根据题意，我们得知这是一棵满二叉树，不存在两个点不能互相到达的情况。
做法一：
LCA思想，我们先计算每个点的深度。首先使两个点先到达同一深度，然后同时向上跳，直到相等为止。
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cmath> using namespace std; int n,a,b,da,db,ans1,ans2; long long read() { long long x=0,f=1; 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; } int main() { freopen("city.in","r",stdin); freopen("city.out","w",stdout); n=read(); for(int i=1;i<=n;++i) { a=read();b=read(); ans1=0;ans2=0; double aa=a; double bb=b; da=1;db=1; while(aa>=1){aa/=2;if(aa>=1)da++;} while(bb>=1){bb/=2;if(bb>=1)db++;} if(da<db){swap(da,db);swap(a,b);} while(da!=db){da--;a>>=1;ans1++;} while(a!=b){a>>=1;b>>=1;ans2++;} printf("%d ",ans1+2*ans2); } return 0; }
做法二：
更优，我们反复对大的数除以2直到相等为止，答案就是操作次数