分形之城（递归）

题目：

分析

一般这种题都有一定得规律，根据观察可以发现， N = 2，是复制或复制旋转才得到结果。

这里先说一下线性代数中旋转后的坐标计算公式

运用矩阵乘法计算旋转后的（x , y）

然后就进行如图所示的操作

由于图片过大无法放大，所以查看图片请访问：https://img2020.cnblogs.com/blog/1938255/202004/1938255-20200413013807377-2043893218.png

然后写代码，递归为子问题

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cmath>
  5 using namespace std;
  6 typedef long long ll;
  7 typedef pair<ll, ll> PLL;
  8 PLL calc(ll n, ll m){
  9     if(n == 0) return make_pair(0,0);
 10     ll len = 1ll << n - 1, cnt = 1ll << 2 * n -2;//len为边长的一半，cnt为一个子块的城区数 
 11     pair<ll,ll> pos = calc(n-1, m % cnt);//递归成子问题然后推出问题 
 12     ll x = pos.first, y = pos.second;
 13     ll z = m/cnt;
 14     if (z == 0) return make_pair(y,x);
 15     if (z == 1) return make_pair(x,y + len);
 16     if (z == 2) return make_pair(x + len, y + len);
 17     return make_pair(2 * len - 1 - y, len - 1 - x);
 18 
 19 }
 20 int main(){
 21     int t;
 22     cin >> t;
 23     while(t--){
 24         ll N, A, B;
 25         cin >> N >> A >> B;
 26         pair<ll,ll> ac = calc(N, A-1);//求出A-1是保证在对应的子块中 
 27         pair<ll,ll> bc = calc(N, B-1);
 28         double x = ac.first - bc.first, y = ac.second - bc.second;
 29         printf("%.0lf
", sqrt(x*x + y*y) * 10);
 30     }
 31     return 0;
 32 }

追求吾之所爱