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

· · 题解

题意：

给了一个斐波那契螺旋，就是许多正方形构成的一个图形。\ 由此就容易想起 P1003 [NOIP 2011 提高组] 铺地毯，因为可以抽象这些正方形为地毯。

思路：

由于斐波那契数列增长速度极快，所以打表可知在第九十多个正方形时便超过数据范围。\ 而最多有十万个询问，故不会超时。\ 于是便可枚举每个正方形并判断其是否包含查询点。\ 所以最后的问题便变成了枚举正方形。

枚举方法：

  1. 判断其是朝哪个方向，可用取余。
  2. 每次只需要得出右上角或左下角便可判断，因为此为正方形。
  3. 由图找每个点变化 剩下请见代码写法。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b;
int T;
LL u,v;
LL fb[100];
int main(){
//  freopen("fibonacci3.in","r",stdin);
//  freopen("fibonacci3.out","w",stdout);
    fb[1]=1;
    fb[2]=1;
    for(int i=3;i<=92;i++)fb[i]=fb[i-1]+fb[i-2]/*,printf("%lld\n",fb[i])*/;//92次 

    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&u,&v);
        LL x=-1,y=0,s=0,t=1;
        for(int i=1;i<=92;i++){
    //      printf("%lld %lld %lld %lld\n",x,y,s,t); 
            if(x<=u&&y<=v&&u<=s&&v<=t){
                printf("%lld\n",fb[i]);
                break;
            }
            if(i%4==1){
                if(i!=1)s=x+fb[i+1];
                t=y;
                x=x,y-=fb[i+1];
            }else if(i%4==2){
                x+=fb[i],y=y;
                s+=fb[i+1],t=y+fb[i+1];
            }else if(i%4==3){
                y=t,x=s-fb[i+1];
                s=s,t+=fb[i+1];
            }else if(i%4==0){
                s=x,t=t;
                x=s-fb[i+1],y=t-fb[i+1];
            }//纯看图写，不想思考了。
        } 
    }
    return 0;
}

完结撒花