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

G1yu · 2025-10-25 19:13:24 · 题解

思路

非常非常简单的暴力啊。

我们对于每个斐波那契正方形，预处理出各个正方形的左下角 X_i 和右上角 ed_i，对于每次询问 x,y，我们找到满足 X_{st_i} \leq x \leq X_{ed_i},Y_{st_i} \leq y \leq Y_{ed_i} 的最小的 i 并输出即可。

注意，只需要预处理 91 个正方形即可，为了保险，建议使用 __int128 存储 st,ed，总时间复杂度 O(91n)。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N =1e5+5,inf = 2e9,memse = 0x3f;
using pii = pair<__int128,__int128>;
pii st[N],ed[N];
ll fib[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    st[1] = {-1,0},st[2] = {-1,-1},st[3] = {0,-1},st[4] = {-1,1};
    ed[1] = {0,1},ed[2] = {0,0}, ed[3] = {2,1},ed[4] = {2,4};
    fib[0] = 0,fib[1] = 1;
    for(int i=2;i<=91;i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    for(int i=5;i<=91;i++){
        if(i % 4 == 1){
            st[i] = {st[i-1].first - fib[i],ed[i-1].second - fib[i]};
        }
        if(i % 4 == 2){
            st[i] = {st[i-1].first,st[i-1].second - fib[i]};
        }
        if(i%4==3){
            st[i]={st[i-1].first + fib[i-1],st[i-1].second};
        }
        if(i % 4 == 0){
            st[i]={ed[i-1].first-fib[i],ed[i-1].second};
        }
        ed[i] = {st[i].first + fib[i] ,st[i].second + fib[i]};
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        for(int i=1;i<=91;i++){
            if(st[i].first <= x &&ed[i].first>= x && st[i].second <= y && ed[i].second >= y){ cout<<fib[i]<<'\n';break;}
        }
    }
    return 0;
}