problem
- 给你一个原始的分形图
- t组数据,对于每组数据,输入3个数n,h,o (n为在第n级,h,o为两个房子的编号)
- 求在第n级情况下,编号为h和o的两个点之间的距离*10为多少
其中,第n级分形图形成规则如下:
1. 首先先在右下角和右上角复制一遍n-1情况下的分形图
2. 然后将n-1情况下的分形图逆时针旋转90度,放到左上角
3. 最后将n-1情况下的分形图顺时针旋转90度,放到左下角
编号是从左上角那个点开始计1,沿着道路计数。
solution
递归边界
当n等于1时(即是最初的那个第1级分形图)
1.当s等于1,x=1,y=1
2.当s等于2,x=1,y=2
3.当s等于3,x=2,y=2
4.当s等于4,x=2,y=1递归过程
1.当前编号小于上一级编号总数时
该情况说明当前编号是在n级分形图的左上角,
但是左上角分形图是n-1级分形图逆时针旋转90度得到的
顾我们带入递归式时,需要将x和y,倒一下
不明白的同学可以这样看:
第1级道路:(1,1)->(1,2)->(2,2)->(2,1)
第2级道路左上角:(1,1)->(2,1)->(2,2)->(1,2)
两种情况的x和y情况互换了
递归式: rec(n-1,s,y,x);
2.当编号小于2倍的n-1数目时,说明当前编号s在分形图的右上角
由于右边的分形图没有经过旋转
所以我们直接带入递归式,
需要注意的是我们的编号要减去上一级的编号,
因为我们始终是根据上一级来推出下一级
递归式:rec(n-1,s-p[n-1],x,y);
递归出来之后,我们的x需要加上上一级的边的大小
这从分形图中很容易看出
即x=x+(1<<n-1);
3.当编号小于3倍的n-1数目时,跟第2种情况类似,
只是递归出来之后,x和y都需要加上上一级的边的大小
即
rec(n-1,s-2*p[n-1],x,y);
//注意编号必须要小于上一级的大小
// 因为我们是放在上一级的情况下考虑的
x+=(1<<n-1);
y+=(1<<n-1);
4.最后一种情况,s在第n级分形图的左下角
这种情况跟第2种情况差不多,
我们先按照逆时针的情况来解决,这就跟第2种情况一样了
然后比较坐标x和y的关系,
容易看出,顺时针相比于逆时针
x映射为(1<<n)+1-x
y映射为(1<<(n-1))+1-y
可以观察分形图,这个地方有点难理解
可以比较坐标来理解codes
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
void calc(int n, LL id, LL &x, LL &y){
if(n == 1){
if(id==1)x=1,y=1;
if(id==2)x=1,y=2;
if(id==3)x=2,y=2;
if(id==4)x=2,y=1;
}else{
LL _id = (1<<(n-1))*(1<<(n-1));
if(id <= _id){
calc(n-1,id,y,x);
}else if(id <= 2*_id){
calc(n-1,id-_id,x,y);
y += 1<<(n-1);
}else if(id <= 3*_id){
calc(n-1,id-2*_id,x,y);
x += 1<<(n-1);
y += 1<<(n-1);
}else{
calc(n-1, id-3*_id, y,x);
x = (1<<n)+1-x;
y = (1<<n-1)+1-y;
}
}
}
int main(){
int _w; scanf("%lld", &_w);
while(_w--){
int n; LL h,o;
scanf("%d%lld%lld", &n, &h, &o);
LL sx, sy, ex, ey;
calc(n,h,sx,sy);
calc(n,o,ex,ey);
printf("%.0f
",sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))*10);
}
return 0;
}