题解：P14308 【MX-S8-T1】斐波那契螺旋

题意

给定一个坐标系，其中包含斐波那契螺旋及其组成，随后给定若干个坐标，问你这些点处于哪个斐波那契螺旋所在的正方形内。

思路

其实题面已经给了一定的提示，只要确定了一个正方形左下角的点和边长，这个正方形就能在坐标系中确定了。求边长很简单，求斐波那契数列即可。关键的难点在于求左下角点的坐标。

那么我们如何求这个点的坐标呢？

看看下面这张图：

按“边长 : 左下角点坐标”的格式列出来如下：

CPP

1 : (-1, 0)
1 : (-1, -1)
2 : (0, -1)
3 : (-1, 1)
5 : (-6, -1)
8 : (-6, -9)
13 : (2, -9)
21 : (-6, 4)

乍一看... 好像什么也看不出来。

但倘若我们把两个点的坐标之差算出来呢？

CPP

1 : (-1, 0) Δx=-1 Δy=0
1 : (-1, -1) Δx=0 Δy=-1
2 : (0, -1) Δx=1 Δy=0
3 : (-1, 1) Δx=-1 Δy=2
5 : (-6, -1) Δx=-5 Δy=-2
8 : (-6, -9) Δx=0 Δy=-8
13 : (2, -9) Δx=8 Δy=0
21 : (-6, 4) Δx=-8 Δy=13

是不是感觉初见端倪了？这里面的差值又有

13

，又有

8

，又有

5

，肯定和斐波那契数列脱不了关系。

如果还是理解不了，那么再看下面这张图：

在跳点的过程中，我们发现差值的正负变化存在周期性，横坐标的变化遵从“负零正负”，而纵坐标的变化遵从“负负零正(除了第一次为‘零负零正’)”。

我们继续观察上图，可以进一步找寻规律。对于每个周期：

第一次跳点中，横坐标变化量的绝对值等于当前正方形的边长，纵坐标变化量的绝对值等于上一个周期第四次跳点纵坐标变化量的绝对值(第一个周期为

0

)。

第二次跳点中，横坐标变化量的绝对值等于

0

(纵向跨越，所以横坐标不变)，纵坐标变化量的绝对值等于当前正方形的边长。

第三次跳点中，横坐标变化量的绝对值等于上一个正方形的边长，纵坐标变化量的绝对值等于

0

(横向跨越)。

第四次跳点中，横坐标变化量的绝对值等于上一个横坐标变化量的绝对值，纵坐标变化量的绝对值等于上一个正方形的边长。

把所有点处理完毕后，所有正方形位置也就确定了。于是对于每个点，我们从小到大遍历所有正方形，检查这个点是否在正方形内，最后输出这个正方形边长就可以了。

Code

CPP

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
ll t, x, y, fbs[120], pos[120][2]; // 数组开大一点以防万一
int main()
{
    fbs[1] = 1LL;
    fbs[2] = 1LL;
    for(ll i = 3;i <= 119;i++) fbs[i] = fbs[i - 1] + fbs[i - 2]; // 预处理斐波那契数列
    for(ll i = 1;i <= 119;i++){ // 定位正方形
        ll del1, del2;
        // 计算差值
        if((i - 1LL) % 4LL == 0LL){
            del1 = -fbs[i];
            if(i == 1LL) del2 = 0LL;
            else del2 = -fbs[i - 2];
        }
        else if((i - 1LL) % 4LL == 1LL){
            del1 = 0LL;
            del2 = -fbs[i];
        }
        else if((i - 1LL) % 4LL == 2LL){
            del1 = fbs[i - 1];
            del2 = 0LL;
        }
        else if((i - 1LL) % 4LL == 3LL){
            del1 = -fbs[i - 2];
            del2 = fbs[i - 1];
        }
        pos[i][0] = pos[i - 1][0] + del1;
        pos[i][1] = pos[i - 1][1] + del2;
    }
    scanf("%lld", &t);
    while(t--){
        scanf("%lld%lld", &x, &y);
        for(ll i = 1;i <= 119;i++){
            ll xa = pos[i][0], ya = pos[i][1]; // 左下角点坐标
             ll xb = pos[i][0] + fbs[i], yb = pos[i][1] + fbs[i]; // 右上角点坐标
            if(x >= xa && x <= xb && y >= ya && y <= yb){
                printf("%lld\n", fbs[i]); // 若被正方形包围，则输出边长
                break;
            }
        }
    }
    
    return 0; // 结束 (｡･ω･｡)
}

题解：P14308 【MX-S8-T1】斐波那契螺旋

文章操作

题意

思路

Code

相关推荐

评论

题解：P14308 【MX-S8-T1】斐波那契螺旋