AcWing 4305. 斐波那契字符串
原题链接
简单
作者:
Bear_King
,
2022-09-26 09:41:43
,
所有人可见
,
阅读 270
基于斐波那契数列的模拟题
注意:一般有一定数据范围的斐波那契问题,推荐用地推来做,如果不要求时间复杂度直接地归2行搞定爽歪歪
这道题就不行,首先绝对不能把斐波那契前100或1000项全保存起来,因为超过50的项一般都会爆int,开longlong的话,就用不成数组模拟哈希表做不到预处理,所以审题最关键,题目看明白了,就不用一顿梭哈把自己带坑里
既然这道题只需要输出前n项,符合为O,不符合为o,那就直接预处理小于等于1000以内的所有斐波那契,然后一个for循环就欧克了
#include <iostream>
#include <stdio.h>
using namespace std;
int a[1010]; //根据数据范围定义数组长度
int main()
{
//输入一个n,返回斐波那契数列第n项的元素
int n;
scanf("%d", &n);
//审题以后,我们就知道只需要预处理1000以内所有符合斐波那契的数值标记即可
//注意:如果你要输出1000个斐波那契就直接炸了,比如第85项直接炸int了
int f1 = 1,f2 = 1,f3 = 1;
while(f3 <= 1000)
{
a[f3] = 1;
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
//前面已经把1000以内所有符合条件的数值都标记了,直接输出就行了
for(int i = 1;i <= n;i ++)
if(a[i]) printf("O");
else printf("o");
return 0;
}