POJ3889 Fractal Streets

由于自己一直不刷题,越来越菜,为了拒绝躺平,我决定刷刷题!

题意

现在我们要负责城市扩建的规划工作。建筑位于每个格子的正中间。原来(n=1时)的城市是如下图(a)一样的排列(这里的布局强调的是两个建筑之间道路的规划)。
对于n时,扩建的方案是把n-1时的城市布局原封不动复制一遍放到正上方,然后原来的布局分别逆时针和顺时针旋转90度放到左上方和左方。比如n=2的布局,原先n=1的布局位于整个布局的右下角,经过变换得到了如图(b)的模样。n=3同理,为图(c)。

现在我们对于每个n,从左上角开始沿着道路从1开始编号。问在n时,编号为S的建筑和D建筑之间直线距离有多远。

范围满足n<16xy不超过int范围。

分析

显然这是个模拟,所幸n不大。

问题的关键在于我们如何知道S和D在图中的具体坐标。如果我们知道坐标了,那求直线距离不就是洒洒水。
欸?我们要求坐标。那我们显然要建立一个合适的坐标系,坐标系咋建也是个问题。这个问题先放一放。

题目里说建筑编号从1开始,我们为了方便,编号从0开始,每个编号都减1
下面说的所有编号都是减了1的编号!

1. n>1时,图形可以分成四个部分

比如看n=2的图(b),我们显然可以发现他可以均分为四个部分,每个部分都是由n=2-1=1变换过来的。
基于这个思路,我可以这么认为:其实对于一个n的图形,我只关注右下角这部分就可以了。因为根据题意,其他三个部分肯定是右下角旋转平移变出来的。

然后我还能发现,对于每个n,一共有4^n个建筑,每一块就是除以4也就是有4^(n-1)个建筑,我们把每一块的建筑数量设为W
那么对于X号建筑,它在哪个区域?其实只需要X/W就能求出来了。0代表左上角,1代表右上角,2代表右下角,3代表左下角。我们也这样来称呼四个区域吧。

这里我们再提出一个概念,叫域内编号。
比如图(b),4号点在1号区域内,它的域内编号,也就是在它所在的1号区域内的编号是X%W

对于每个区域,他的边长是E,显然E=sqrt(W)

2. n=1时,四个点的坐标

我发现无论n是多少,右下角那四个2*2的点永远是永恒不表的。追根溯源,它来自于n=1的情况。
假如我们把坐标系原点设在右下角那个建筑点上,右下角的建筑是(0,0),无论n是多少都是这样,这可以给我们带来递归意义上的便利,不信往后看就懂了。
那么n=1时,0号点坐标是(1,1),1是(0,1),2是(0,0),3是(1,0)。

3. n=2时,每个部分的建筑坐标怎么求

先不多说,分析对于n=2这种特殊情况。对于四个部分而言:

先说最简单的1和2两个区域:

  1. 对于2号部分,这一部分四个点坐标就是n=2-1=1的坐标点,根本不用求。
  2. 对于1号部分,求这一部分的点不如先求2号部分,然后给他平移上去就行了。比如1号区域域内编号为X的点,在2号区域对应的点的域内编号恰好也是X,先把2号区域内的X坐标求出来,然后往上平移E就行了。

我显然可以发现,对于0,1,3这三个部分,它的点的坐标都可以采用在2号区域内找对应点,通过数学几何变换的方法找到对应坐标的方法,这就是这个题的核心做法了

然后是0和3区域,这俩区域有点难,因为还涉及到旋转了。
这里还不得不想这样的一个问题:在0号区域或者3号区域内的一个点,如果域内编号是X,那它在2号区域对应点的域内编号是多少?
答案是W-X-1,也就是在0号区域里的第0个点,其实是由2号区域里的第W-1,也就是2号区域最后一个点变过来的,不信你可以转一下试试。对于3号区域也是这样的。

知道了这个思路,0和3求起来思路就容易了,先找到对应点,求对应点坐标,然后这个点绕2号区域的中心做对应的旋转,这里是一个纯粹的数学问题。然后平移一下就可以了。

3. n>2时的拓展

分析完了n=2,那么n>2其实也是这样的。我们先找到各个部分对应2号区域内的点的坐标,做变换就行了。
变换对于1号区域只是一个平移,但是0和3需要先旋转再平移。

然后你就会发现,在2号区域里找坐标,其实问题能转换为n-1里的问题,n-1的问题要解决,也需要找它的右下角,又转换为了n-2的问题,直到n=1。
显然这是一个递归!

好了,现在我们思路就清晰了,可以敲代码了。

代码

#include<iostream>
#include<cmath>
#include<utility>

using namespace std;

#define x first
#define y second

typedef pair<int,int> pp;

pp getPos(int n, int x){
    if(n==1){
        switch(x){
            case 0: return make_pair(1,1);
            case 1: return make_pair(0,1);
            case 2: return make_pair(0,0);
            case 3: return make_pair(1,0);
        }
        return make_pair(0,0);
    } else {
        int ucnt = (int)pow(4.0,n-1);
        int edge = (int)pow(2.0,n-1);
        int a = x/ucnt;
        int idx = x % ucnt;

        if(a==0){
            int subidx = ucnt - idx - 1;
            pp loc = getPos(n-1, subidx);
            return make_pair(-loc.y+edge-1+edge, loc.x+edge);
        } else if(a==1){
            pp loc = getPos(n-1,idx);
            return make_pair(loc.x,loc.y+edge);
        } else if(a==2){ 
            return getPos(n-1,idx);
        } else if(a==3){
            int subidx = ucnt - idx - 1;
            pp loc = getPos(n-1, subidx);
            return make_pair(loc.y + edge , -loc.x+edge-1);
        }
        return make_pair(0,0);
    }
}

double dis(pp a, pp b){
    return sqrt( (a.x-b.x)*(a.x-b.x)*1.0 + (a.y-b.y)*(a.y-b.y)*1.0 ); 
}

double solve(int n, int s, int d){
    s-=1; d-=1;
    pp a = getPos(n,s), b=getPos(n,d);
    return dis(a,b)*10;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,s,d;
        cin>>n>>s>>d;
        printf("%.0lf\n", solve(n,s,d));
    }
    return 0;
}

后记

这道题在POJ上交的。POJ的gcc有亿点老,麻麻的,它sqrt和pow不能填int,只能填double,把我坑惨了。
我CE了好几发都一脸懵逼,属实是本地没事,交了就CE。

上一篇
下一篇