【题解】分形之城

题目链接

做题感受

这道题目对于我这种没学过线性代数的初中生来说烧脑至极,什么坐标旋转啥的都不会,就在acwing上听y总讲。

最要命的是y总还用数组坐标代替直角坐标系的坐标讲,于是我就云里雾里的。。。

解题思路

预计pj1=水平做题时间:2h+(如果能做出来的话),看题解时间:1h+。

这道题目很明显是将一个大区域分成了4个小区域,并且四个小区域的旋转方向不同,所以我们需要进入每一个小区域看。

我们递归到了最小的区域,也就是题目中的图一,可以由它转移出在图二中的位置。以此类推从部分回到全局。

当我们递归的时候,我们需要将这个东西在每一块大小的图中的编号计算出来。

旋转

顺时针旋转 $\theta$ 度公式:

$$ \\ \left[ \begin{array}{ccc} cos\theta & sin\theta\\ -sin\theta & cos\theta \end{array} \right] $$

若我讲的不清楚,请仔细听y总视频,你会受益匪浅

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct p{
    LL x,y;
};
p calc(LL n,LL m){
    if(n==0) return {0,0}; //
    LL len=1ll<<(n-1),cnt=1ll<<(2*n-2);
    p pos=calc(n-1,m%cnt);
    LL x=pos.x,y=pos.y;
    LL z=m/cnt;
    if(z==0)return {y,x};
    if(z==1)return {x+len,y};
    if(z==2)return {x+len,y+len};
    if(z==3)return {len-1-y,2*len-1-x};//先旋转,再翻折,再平移。翻折的原因是它的入口不同
}
int main(){
    int t;
    cin>>t;
    while(t--){
        LL a,b,n;
        cin>>n>>a>>b;
        p pos1=calc(n,a-1);//变化为0到(1<<n*2)-1
        p pos2=calc(n,b-1);
        double dx=abs(pos1.x-pos2.x),dy=abs(pos1.y-pos2.y);

        printf("%.0lf\n",sqrt(dx*dx+dy*dy)*10);
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/665/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者