J Fibonacci Cane

湖南省第十八届大学生计算机程序设计竞赛（HNCPC2022）J题

原题链接：https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1198

没错，这个题是签到题：判断斐波那契区间有没有一段的和等于n，由于n≤1e15，所以直接暴力求解。

题解代码如下

#include<iostream>

using namespace std;

typedef long long ll;

ll f[110];  //自己百度斐波那契数列前一百项，就知道为啥空间足够了。
int cnt;

void init()
{
	f[1] = 1, f[2] = 1;
	cnt = 2;
	while (f[cnt] <= 1e15)
	{
		f[cnt + 1] = f[cnt] + f[cnt - 1];  //将小于等于1e15的斐波那契数放入数组。
		cnt++;
	}
}
int main()
{
	init();
	ll n;
	while (scanf("%lld", &n)!=EOF)//题目输入要求
	{
		bool ok = false;
		for (int i = 1; i <= cnt; i++)
		{
			ll sum = 0;
			for (int j = i; j <= cnt; j++)
			{
				sum += f[j];
				if (sum == n)
				{
					ok = true;
				}
				else if (sum > n) break;  //当sum大于n时就没必要内部循环相加了，因为sum一直是递增。
			}
		}
		if (ok)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

本人蒟蒻，若有不对或不恰当之处，还望指正，感谢观看我的博客