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

· · 题解

标准签到题，几乎没有思维难度，非常符合 S 组的风格。

数据范围放在那里就是搞笑的，斐波那契数列在 70 项以内就可以超过 10^{18}，所以直接根据题意模拟正方形的变化，然后如果成功覆盖就输出答案即可。

具体的，用数字 d 表示当前正方形下一步往哪个方向扩展：0 为向下，1 为向左，2 为向上，3 为向右。一开始方向为 0。

记 (lx,ly),(rx,ry) 分别表示左下角、右上角坐标，c 为当前边长，b,a 分别为前一个、前两个正方形的边长。

稍微分析可得：

每扩展一步就检查是否成功覆盖，输出答案即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,x,y;
bool check(int a,int b,int c,int d){return (a<=x&&x<=c&&b<=y&&y<=d);}
void solve(){
    cin>>x>>y;
    if (x>=-1&&x<=0&&y>=-1&&y<=1){//特判前两个
        cout<<"1\n";
        return;
    }
    int lx=0,ly=-1,rx=2,ry=1,d=2,a=1,b=1,c=2;//注意，这里从第三个正方形开始
    while (!check(lx,ly,rx,ry)){
        int tmp=c;
        c+=b,a=b,b=tmp;
        if (d==0)ly-=c,ry-=b,rx+=a;
        else if (d==1)lx+=b,rx+=c,ry+=a;
        else if (d==2)ly+=b,lx-=a,ry+=c;
        else lx-=c,ly-=a,rx-=b;
        d=(d+1)%4;
    }
    cout<<c<<endl;
}
signed main(){
    for (cin>>t;t;t--)solve();
    return 0;
}