[[411094]]

本文轉(zhuǎn)載自微信公眾號(hào)「Piper蛋窩」，作者Piper蛋。轉(zhuǎn)載本文請(qǐng)聯(lián)系Piper蛋窩公眾號(hào)。

題目

城市的規(guī)劃在城市建設(shè)中是個(gè)大問題。

不幸的是，很多城市在開始建設(shè)的時(shí)候并沒有很好的規(guī)劃，城市規(guī)模擴(kuò)大之后規(guī)劃不合理的問題就開始顯現(xiàn)。

而這座名為 Fractal 的城市設(shè)想了這樣的一個(gè)規(guī)劃方案，如下圖所示：

當(dāng)城區(qū)規(guī)模擴(kuò)大之后，F(xiàn)ractal 的解決方案是把和原來城區(qū)結(jié)構(gòu)一樣的區(qū)域按照?qǐng)D中的方式建設(shè)在城市周圍，提升城市的等級(jí)。

對(duì)于任意等級(jí)的城市，我們把正方形街區(qū)從左上角開始按照道路標(biāo)號(hào)。

雖然這個(gè)方案很爛，F(xiàn)ractal 規(guī)劃部門的人員還是想知道，如果城市發(fā)展到了等級(jí) ，編號(hào)為 和 的兩個(gè)街區(qū)的直線距離是多少。

街區(qū)的距離指的是街區(qū)的中心點(diǎn)之間的距離，每個(gè)街區(qū)都是邊長(zhǎng)為 米的正方形。

輸入格式

第一行輸入正整數(shù)n ，表示測(cè)試數(shù)據(jù)的數(shù)目。

以下 n行，輸入 n組測(cè)試數(shù)據(jù)，每組一行。

每組數(shù)據(jù)包括三個(gè)整數(shù) N，A， B，表示城市等級(jí)以及兩個(gè)街區(qū)的編號(hào)，整數(shù)之間用空格隔開。

輸出格式

一共輸出 行數(shù)據(jù)，每行對(duì)應(yīng)一組測(cè)試數(shù)據(jù)的輸出結(jié)果，結(jié)果四舍五入到整數(shù)。

數(shù)據(jù)范圍

輸入樣例：

3  
1 1 2  
2 16 1  
3 4 33  

輸出樣例：

10  
30  
50  

題解

這有啥不明白的，手把手畫出來!

首先明確，為啥能用遞歸：

• 我們想計(jì)算 n 等級(jí)的坐標(biāo)，知道 n-1 等級(jí)的坐標(biāo)就行

然后思考怎么遞歸?

咱們首先規(guī)定，每個(gè)等級(jí)的坐標(biāo)系原點(diǎn)是獨(dú)特的，如下圖。

然后我們從特殊到一般，歸納推規(guī)律：

• 等級(jí)1這個(gè)塊塊，如果放到等級(jí)2里，有四種情況要討論
• 等級(jí)1放到等級(jí)2的左上象限，則相當(dāng)于順時(shí)針旋轉(zhuǎn)了 90° ，并且還要沿 y 軸翻轉(zhuǎn)(為什么要沿 y 軸翻轉(zhuǎn)呢?因?yàn)槟阕⒁饷總€(gè)編號(hào)的位置，不翻轉(zhuǎn)，形狀雖然對(duì)上了，但是編號(hào)順序沒對(duì)上)
• 等級(jí)1放到等級(jí)2的右上象限，則不用轉(zhuǎn)
• 等級(jí)1放到等級(jí)2的右下象限，則不用轉(zhuǎn)
• 等級(jí)1放到等級(jí)2的左下象限，則相當(dāng)于逆時(shí)針旋轉(zhuǎn)了 90° ，并且還要沿 y 軸翻轉(zhuǎn)

轉(zhuǎn)完了，因?yàn)槲覀儸F(xiàn)在從等級(jí)1到等級(jí)2了，因此坐標(biāo)系原點(diǎn)也移動(dòng)了，所以要在等級(jí)1的原有坐標(biāo)基礎(chǔ)上進(jìn)行平移。

好了，我給你畫個(gè)圖，你就懂了。

然后你再去看代碼。

這里補(bǔ)充一點(diǎn)數(shù)學(xué)知識(shí)：

• 對(duì)于點(diǎn) (x, y) ，沿原點(diǎn)順時(shí)針旋轉(zhuǎn) 90° ，將變?yōu)?(y, -x)
• 對(duì)于點(diǎn) (x, y) ，沿原點(diǎn)逆時(shí)針旋轉(zhuǎn) 90° ，將變?yōu)?(-y, x)
• 對(duì)于點(diǎn) (x, y) ，以 y 軸為對(duì)稱軸翻轉(zhuǎn)將變?yōu)?(-x, y)

代碼

#include <iostream> 
#include <cstring> 
#include <cmath>  // sqrt 
#include <algorithm> 
 
using namespace std; 
 
typedef long long LL; 
typedef pair<LL, LL> PLL; 
 
PLL calc(LL n, LL m) 
{ 
    /* 
    * n: 等級(jí) 
    * m: 坐標(biāo)，從0開始計(jì)數(shù) 
    */ 
    if (n == 0) return {0, 0}; 
    LL len = 1ll << (n - 1);  // 2^{n-1} 本等級(jí)內(nèi)象限的邊長(zhǎng)/2 
    LL cnt = 1ll << (2 * n - 2);  // 4^{n-1} 本等級(jí)內(nèi)象限容量 
    PLL pos = calc(n - 1, m % cnt);  // 上一等級(jí)的坐標(biāo)信息 
    LL x = pos.first, y = pos.second; 
    int z = m / cnt;  // 處于哪個(gè)象限 
    // 左上象限順轉(zhuǎn)90°（y,-x）沿y對(duì)稱（-y,-x）更換原點(diǎn)（-y-len,-x+len） 
    if (z == 0) 
        return { - y - len, - x + len }; 
    // 右上象限更換原點(diǎn)（x+len,y+len） 
    else if (z == 1) 
        return { x + len, y + len }; 
    // 右下象限更換原點(diǎn)（x+len,y-len） 
    else if (z == 2) 
        return { x + len, y - len }; 
    // 左下象限逆轉(zhuǎn)90°（-y,x）沿y對(duì)稱（y,x）更換原點(diǎn)（y-len,x-len） 
    return { y - len, x - len }; 
} 
 
int main() 
{ 
    int N; 
    cin >> N; 
    while (N --) 
    { 
        LL n, m1, m2; 
        cin >> n >> m1 >> m2; 
        PLL pos1 = calc(n, m1 - 1); 
        PLL pos2 = calc(n, m2 - 1); 
 
        double delta_x = (double) (pos1.first - pos2.first); 
        double delta_y = (double) (pos1.second - pos2.second); 
        // 等級(jí)1中 len 是單位長(zhǎng)度，且表示象限的一半長(zhǎng)即為 10 / 2 = 5 
        printf("%.0lf\n", sqrt(delta_x * delta_x + delta_y * delta_y) * 5); 
    } 
} 

參考資料

[1]Acwing: https://www.acwing.com

[2]98. 分形之城: https://www.acwing.com/problem/content/100/