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

题意：

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

思路：

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

枚举方法：

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

AC 代码：

CPP

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

~~完结撒花~~

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

文章操作

题意：

思路：

枚举方法：

AC 代码：

相关推荐

评论

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