分形之城 题解
作者:方彦哲
Fesdrer
感谢观看!!!
题目
没看题目的自己看
满分算法
(分治+递归) $O(n)$
为了方便描述,我们将题目中的房屋编号都减去1,行号列号都从0开始,$n$、$A$、$B$都减去1。
题目关键想让我们求出街区编号为$A$、$B$的行号$x$和列号$y$。通过对题目的观察,我们发现,每一个$n$级城市都可以由4个$n-1$级城市拼接而成,其规模为$4^n$。以街区$A$为例,我们可以先递归求出街区$Amod4^{n-1}$在$n-1$级城市的行号列号$(x_0,y_0)$,通过运算求出其在$n$级城市的行号列号。
1.当$A/4^{n-1}=0$即$A$位于左上角时,观察发现其沿着左上-右下一轴翻转,最终坐标为$(y_0,x_0)$。
2.当$A/4^{n-1}=1$即$A$位于右上角时,其最终坐标为$(x_0,y_0+2^{n-1})$。
3.当$A/4^{n-1}=2$即$A$位于右下角时,其最终坐标为$(x_0+2^{n-1},y_0+2^{n-1})$。
4.当$A/4^{n-1}=3$即$A$位于左下角时,观察发现其沿着右上-左下一轴翻转,最终坐标为$(2^n-y_0-1,2^{n-1}-x_0-1)$。
在求出AB街区的坐标后,通过勾股定理就可以求出答案了。注意要$*10$!!!
时间复杂度 $O(n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
pair<long long,long long> calc(long long n,long long m){
if(n==0) return make_pair(0,0);
long long len=(long long)1ll<<(n-1),cnt=(long long)1ll<<(2*n-2);
pair<long long,long long> pos=calc(n-1,m%cnt);
long long x=pos.first,y=pos.second;
long long z=m/cnt;
if(z==0) return make_pair(y,x);
if(z==1) return make_pair(x,(long long)y+len);
if(z==2) return make_pair((long long)x+len,(long long)y+len);
if(z==3) return make_pair((long long)2*len-y-1,(long long)len-x-1);
}
long long printfs(double lon){
if(lon<(long long)(lon)+0.5) return (long long)(lon);
else return (long long)(lon)+1;
}
long long t,lv,a,b;
int main(){
cin>>t;
while(t--){
cin>>lv>>a>>b;
a-=1,b-=1;
pair<long long,long long> aa=calc(lv,a),bb=calc(lv,b);
double _3=(long long)aa.first*1.0-bb.first*1.0;
double _4=(long long)aa.second*1.0-bb.second*1.0;
double longs=sqrt(_3*_3+_4*_4);
longs*=10;
printf("%lld\n",printfs(longs));
}
return 0;
}