分形之城(算法竞赛进阶指南题目)个人理解与做法

原题链接: 98. 分形之城 - AcWing题库

首先是做这个题中获得的经验:

1.要求出2的次方,不需要预处理或者用pow函数,直接利用位运算即可

2.int的范围是最大2^31-1而不是2^32-1

3.学会了,要函数要返回两个值的时候,不必作为参数加&符号传过去,可以用结构体或者pair定义函数,就可以返回两个相连的变量

我个人的做法比较麻烦,先介绍一下我自己的做法:

例如对于等级3的城市:它可以分为四块,左上为0,右上为1,右下为2,左下为3,设向右为x轴,向下为y轴,第一个房子的坐标为(1,1)

找出第a个房子在等级3的坐标的步骤:

1.先求出a在四块中的哪一块,即为(a-1)/16,16为每一块区域中的房子个数(2^(n-1)),a-1的原因是为了处理边界情况,例如房子标号为16,16/16=1,但是实际上16标号在第0块区域.

2.求出该房子在该分块中的坐标:  例如该房子在第0块区域,以第2块区域为标准,第0块区域是由第2块区域顺时针旋转变化而来,第0块中的第一个房子对应第2块中标号为16的房子,第0块区域中第2块房子对应第二块区域中标号为15的房子..... 两者相加等于17(每个区块中房子数量+1).

以第0块中的第一个房子为例,它对应区块2中的第16个房子,由顺时针变换观察可知,第二块中的第16个房子的x坐标等于第0块中第一个房子的y坐标,第0块中第一个房子的x坐标+第二块中的第16个房子的y坐标=17,因此求第0块中第一个房子的坐标即为求第二块中的第16个房子的坐标

3.递归处理,递归到n==1,如果a=0 x=1 y=1 ,a=1 则x=2,y=1 ,a=2 则x=2,y=2 , a=3则 x=1,y=2;  

递归传回第0块中的第一个房子在第0块中的位置, 因为在第0块 则在等级3城市中的坐标即为在第0块的坐标,  若是在第1块,则在等级三城市的坐标即为在第1块的坐标的x+4,y  与此类似 可求出若在第二块或者第三块区域的坐标

本来打算写一下别人的思路,但是快写完了,又重新看了一下,发现我还并没有完全理解别人的思路,就不写了

代码:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;


pair<long long,long long> check(int n,long long a){
	if(n==1){
		if(a==1||a==4)return {1,(a+1)/2};
		else return {2,(a+1)/2};
	}

	long long t= 1ll<<(n-1)*2;
	long long tt=1ll<<(n-1);
	int z=(a-1)/t;
	a-=z*t;
	if(z==0){
		auto s=check(n-1,t+1-a);
		int x=s.first,y=s.second;
		return {tt+1-y,x};
	}else if(z==1){
		auto s=check(n-1,a);
		int x=s.first,y=s.second;
		return {x+tt,y};
	}else if(z==2){
		auto s=check(n-1,a);
		int x=s.first,y=s.second;
		return {x+tt,y+tt};
	}else if(z==3){
		auto s=check(n-1,t+1-a);
		int x=s.first,y=s.second;
		return {y,tt+1-x+tt};
	}
}

int main(){
	int n;
	cin>>n;
	while(n--){
		int N;
		long long A,B;
		cin>>N>>A>>B;
		auto ans=check(N,A);
		auto ans2=check(N,B);
		long long ax=ans.first,ay=ans.second,bx=ans2.first,by=ans2.second;
		double xx=ax-bx,yy=ay-by;
		printf("%.0lf\n",sqrt(xx*xx+yy*yy)*10);


	}
	return 0;
}

第一次写题解,自己都感觉自己讲的不好(汗)