POJ3889 Fractal Streets
|
6,917
|
题解
|
tdiant

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

题意

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

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

范围满足n<16，x与y不超过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。

上一篇
下一篇