算法:分治递归
时间复杂度:$T·\log_{4}{n}$
需要注意
(1)为了计算方便,将房屋的编号都减去1,编号从0开始
(2)0号和3号的坐标需要画图(或者用数学的方法)求出坐标变换
C++代码
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
PII get_location(int n,LL m)
{
if(!n)return {0,0};
//block 每一个子区间的标号的数量 len每个子区间边的长度
LL block=1ll<<2*n-2,len=1ll<<n-1;
//求出下一级的坐标
auto p=get_location(n-1,m%block);
int x=p.first,y=p.second;
int z=m/block;
//对四个区域进行坐标变换
if(!z)return {y,x};
else if(z==1)return {x,y+len};
else if(z==2)return {x+len,y+len};
return {2*len-1-y,len-1-x};
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
LL a,b;
cin>>n>>a>>b;
auto p=get_location(n,a-1);
auto q=get_location(n,b-1);
double x=p.first-q.first;
double y=p.second-q.second;
printf("%.0lf\n",sqrt(x*x+y*y)*10);
}
return 0;
}