原题链接
考察:分治
令人呕吐的分治
思路:
直观思路是找到A,B的直角坐标,然后求距离和.这里的分治是递归到最底层,然后根据等级i到等级i+1的坐标变化,算出直角坐标.可以发现将图分为4个模块时,每个等级的变换规则相同.
Code
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
PII calc(int n,LL a)
{
if(!n) return {0,0};
LL len = 1ll<<n,mid = 1ll<<n-1;
LL pos = a/(mid*mid);
PII p = calc(n-1,a%(mid*mid));
if(!pos) return {p.second,p.first};
else if(pos==1) return {p.first,p.second+mid};
else if(pos==2) return {p.first+mid,p.second+mid};
else return {2*mid-1-p.second,mid-1-p.first} ;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
LL a,b;
scanf("%d%lld%lld",&n,&a,&b);
PII x = calc(n,a-1);
PII y = calc(n,b-1);
double d = 10*sqrt((x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second));
LL res = d+0.5;
printf("%lld\n",res);
}
return 0;
}