【題目描述】

　　　　

【題目鏈接】

　　　　http://noi.openjudge.cn/ch0204/8463/

【算法】

　　　　為求等級N下的點的坐標可由幾何關系找到其與等級N-1下對應點的關系，然后遞歸直至所有點的祖先（等級0）即可計算出坐標。

【代碼】

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int t; 5 ll n,s,d; 6 pair<ll,ll> calc(int state,ll num) 7 { 8 if(!state) return make_pair(1,1); 9 ll side=1<<(state-1),sum=side*side; 10 ll rec=num/sum,pre_num=num%sum; 11 pair<ll,ll> pr=calc(state-1,pre_num); 12 switch(rec) { 13 case 0: swap(pr.first,pr.second); break; 14 case 1: pr.first+=side; break; 15 case 2: pr.first+=side,pr.second+=side; break; 16 case 3: swap(pr.first,pr.second),pr.first=side-pr.first+1,pr.second=side*2-pr.second+1; 17 } 18 return pr; 19 } 20 int main() 21 { 22 scanf("%d",&t); 23 while(t--) { 24 scanf("%d%lld%lld",&n,&s,&d); 25 pair<ll,ll> p1=calc(n,s-1); 26 pair<ll,ll> p2=calc(n,d-1); 27 ll dx=p1.first-p2.first,dy=p1.second-p2.second; 28 printf("%.0f\n",sqrt(dx*dx*1.0+dy*dy*1.0)*10); 29 } 30 return 0; 31 }

【《算法競賽進階指南》大佬代碼，侵刪】

1 /* 2 Author: Yufei Du 3 本程序僅供參考 4 */ 5 #include <cmath> 6 #include <cstdio> 7 #include <cstring> 8 #include <cstdlib> 9 #include <algorithm> 10 using namespace std; 11 12 pair<__int64, __int64> recur (int stage, __int64 id) 13 { 14 if (stage == 0) return make_pair(0, 0); 15 __int64 max = 1 << (stage - 1), s = max * max; 16 __int64 z = id / s, idsp = id % s; 17 pair<__int64, __int64> psp = recur(stage - 1, idsp); 18 if (z == 0 || z == 3) swap(psp.first, psp.second); 19 if (z == 3) 20 { 21 psp.first = max - psp.first - 1; 22 psp.second = max - psp.second - 1; 23 } 24 if (z == 1 || z == 2) psp.first += max; 25 if (z == 3 || z == 2) psp.second += max; 26 return psp; 27 } 28 int main () 29 { 30 31 int kase; for (scanf("%d", &kase); kase; --kase) 32 { 33 int n; __int64 h, o; 34 scanf("%d %I64d %I64d", &n, &h, &o); 35 pair<__int64, __int64> hp = recur(n, h - 1); 36 pair<__int64, __int64> op = recur(n, o - 1); 37 __int64 dx = abs(hp.first - op.first), dy = abs(hp.second - op.second); 38 printf("%.0f\n", (double)sqrt(dx * dx + dy * dy) * 10); 39 } 40 return 0; 41 }

?

轉載于:https://www.cnblogs.com/Willendless/p/9361879.html

總結

以上是生活随笔為你收集整理的Stupid cat Doge （分形图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。