poj3889 Fractal Streets

原题链接

 

分析:

首先容易通过本题的题意和数据范围看出:这是个递归题。。。

题目让求N级城市中某两个房屋之间的距离,所以就必须先得到两个房屋在城市中的坐标。

在这里我采用的是以类似数组的形式标记坐标,将最左上角的房屋标记为(0,0)。

利用递归的思想,即从原问题出发,不断缩小问题的规模,直到问题的边界,那么我们可以计算两个房屋在第i-1级城市的坐标,通过坐标的变换,从而得到这两个房屋在第i级城市中的坐标。

所以用calc(n,m)来表示在第n级城市中第m个房屋的坐标,先递归计算calc(n-1,m%2^(n-2)),再变换坐标即可。

关于坐标变换:

对于一个房屋(x,y),如果将其围绕原点顺时针旋转90度,得到的新坐标为(y,-x)。逆时针得到坐标为(-y,x)。(注意上面的坐标变换是以数组坐标的形式变换的,如果是数学上的横纵坐标,是相反的结果)

对了,为了防止房屋所在区域计算的混淆,应该先把所有房屋的编号减1,这样就不会再做除法时将不同区域的房屋错看为同一区域。

 

总之,这题的思路很好想,主要难点就在坐标变换上,需要非常细心。。。

 

 

代码:

 

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

typedef long long LL;
typedef pair<LL,LL> pll;

pll calc(LL n,LL m) {
    if (n==0) return make_pair(0,0);
    LL s=1ll<<(2*n-2),len=1<<n-1;
    pll pos=calc(n-1,m%s);
    LL x=pos.first,y=pos.second;
    LL u=m/s;
    if (u==0) return make_pair(y,x);
    else if (u==1) return make_pair(x,y+len);
    else if (u==2) return make_pair(x+len,y+len);
    else if (u==3) return make_pair(2*len-y-1,len-x-1);
}

int main() {
    int t;
    scanf("%d",&t);
    LL n,p,q;
    for (int i=1;i<=t;++i) {
        scanf("%lld%lld%lld",&n,&p,&q);
        pll h=calc(n,p-1);
        pll o=calc(n,q-1);
        double x=h.first-o.first,y=h.second-o.second;
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}

 

 

咳咳。。。第一次写题解。。。。

草,写的真tm乱。。。。

 

上一篇:POJ 3889 Fractal Streets(逼近模拟)


下一篇:hdu1151Air Raid