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

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

数据范围放在那里就是搞笑的，斐波那契数列在

70

项以内就可以超过

10^{18}

，所以直接根据题意模拟正方形的变化，然后如果成功覆盖就输出答案即可。

具体的，用数字

d

表示当前正方形下一步往哪个方向扩展：

0

为向下，

1

为向左，

2

为向上，

3

为向右。一开始方向为

0

。

记

(lx,ly),(rx,ry)

分别表示左下角、右上角坐标，

c

为当前边长，

b,a

分别为前一个、前两个正方形的边长。

稍微分析可得：

$d=0$ ，此时两点变为 $(lx,ly-c),(rx+a,ry-b)$ 。
$d=1$ ，此时两点变为 $(lx+b,ly),(rx+c,ry+a)$ 。
$d=2$ ，此时两点变为 $(lx-a,ly+b),(rx,ry+c)$ 。
$d=3$ ，此时两点变为 $(lx-c,ly-a),(rx-b,ry)$ 。

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

CPP

#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;
}

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

文章操作

相关推荐

评论

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