【算法竞赛进阶指南】POJ3889分形之城

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法竞赛进阶指南】POJ3889分形之城，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1190字，纯文字阅读大概需要2分钟。

内容图文

本道题目是利用递归，去把最后等级1的某个位置求出来，然后回溯向上去把上一等级的相应位置求出来，一般是右下角向左上右上左下扩展，根据旋转的规律回溯计算

城市的规划在城市建设中是个大问题。不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

左上顺时针90°，右上向上反转，左下是逆时针90°

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

pair<long long,long long> calc(long long n,long long m){
    if(n==0) return make_pair(0,0);
    long long len=1<<(n-1),cnt=1<<(2*n-2);//len城市等级-1，cnt为当前等级的城市-1数
    pair<long long,long long> pos=calc(n-1,m%cnt);
    long long x=pos.first,y=pos.second;
    long long z=m/cnt;
    if(z==0) return make_pair(y,x);
    if(z==1) return make_pair(x,y+len);
    if(z==2) return make_pair(x+len,y+len);
    if(z==3) return make_pair(2*len-y-1,len-x-1);
}

int main(){
    int t;
    cin>>t;
    while(t--){
        pair<long long,long long>a,b;
        long long k1,k2,l;
        cin>>l>>k1>>k2;
        a=calc(l,k1-1);//-1代表编号-1，便于处理
        b=calc(l,k2-1);
        double ans=(double)(10*sqrt(1.0*(a.first-b.first)*(a.first-b.first)+1.0*(a.second-b.second)*(a.second-b.second)));
        printf("%.0lf\n",ans);
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的【算法竞赛进阶指南】POJ3889分形之城全部内容，希望文章能够帮你解决【算法竞赛进阶指南】POJ3889分形之城所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---