AcWing-98-分形之城

2021-01-31 · 73次阅读 · 原创 · 数据结构与算法

#递归与递推 #题解

问题

城市的规划在城市建设中是个大问题。

不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。

对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。

输入格式

第一行输入正整数n，表示测试数据的数目。

以下n行，输入n组测试数据，每组一行。

每组数据包括三个整数 N,A,B, 表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出n行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

$1≤N≤31$

$1≤A,B≤2^{2N}$

$1≤n≤1000$

输入样例：

输出样例：

10 
30 
50

思路

用递归的思路去看问题。

等级N的城市由四个等级为N-1的城市构成，其中等级N城市的左上角由等级N-1城市顺时针旋转90度后再水平翻转（其城市的排列顺序的水平方向与翻转前相反）。而等级N城市的右上角由等级N-1城市向上平移而成，与等级N城市的右下角相同。同理，最后等级N城市的左下角由等级N-1的城市逆时针旋转90度再水平翻转所得。具体坐标变化关系可参考下图。

坐标变换图

计算时注意数据范围，避免溢出。

注：可看拓展题-蓝桥杯2020年国赛C++B组F题-皮亚诺曲线

题解

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

typedef long long ll;

pair<ll, ll> calc(int n, ll m) {
    if (n == 0) return make_pair(0, 0);

    ll size = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
    pair<ll, ll> pos = calc(n - 1, m % cnt);
    ll x = pos.first, y = pos.second, z = m / cnt;

    if (z == 0) return make_pair(y, x);       //原位置顺时针90度后再水平翻转，左上角
    if (z == 1) return make_pair(x, size + y);        //原位置，右上角
    if (z == 2) return make_pair(size + x, size + y);      //原位置，右下角
    if (z == 3) return make_pair(size * 2 - y - 1, size - x - 1);   //原位置逆时针90度后再水平翻转，左下角
}


int main() {
    int n, N;
    ll A, B;
    cin >> n;
    while (n--) {
        scanf("%d%lld%lld", &N, &A, &B);

        auto pos_A = calc(N, A - 1);
        auto pos_B = calc(N, B - 1);

        ll dx = pos_A.first - pos_B.first;
        ll dy = pos_A.second - pos_B.second;
        ll ans = ll(sqrt(dx * dx + dy * dy) * 10 + 0.5);
        cout << ans << endl;
    }

    return 0;
}

标题：	AcWing-98-分形之城
链接：	https://www.fightingok.cn/detail/38
更新：	2022-09-18 22:33:25
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可