自动搬运

查看原文

来自洛谷，原作者为

	shame_djj 该怎么办才好呢。。。

搬运于2025-08-24 21:28:42，当前版本为作者最后更新于2019-07-04 18:20:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题作为橙题我觉得技术含量还是挺高的

众所周知 fibonacci数列在第92项时会很大

（用我们教练的话来说就是“long long也救不了你”）

但是fibonacci会在多少项时爆int呢

这是一个问题

于是我们就需要先算一算第几项爆int

这个过程当然是交给计算机来做

由于太简单我就不粘代码了

但是这也体现了我们编程的实用性

用代码来解决实际的问题（而不是仅仅的用来参加算法竞赛什么的）

所以解这道题第一点是算fibonacci

至于第二点怎么模拟就比较简单了

从小到大1的输出

一个简单的贪心思路：从最大的fibonacci数开始选

能选就一直选，直到选不了了

从小到大输出，我们可以通过stack来实现

（当然你也可以直接反着输出）

至此这题就完了

下面奉上我鬼畜的代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <stack>

using namespace std;

long long int f[100] = {1, 1};
stack <int> s;

int main() {
	for (register int i = 1; i <= 45; i ++)
		f[i] = f[i - 1] + f[i - 2];
	int T, n; cin >> T; for (; T; T --) {
		cin >> n; cout << n << '=';
		for (register int i = 45; i >= 1; i --) {
			while (n >= f[i]) s.push(f[i]), n -= f[i];
			if (n == 0) break;
		}
		while (s.size()) {
			if (s.size() == 1) {
				printf ("%d\n", s.top());
				s.pop();
				break;
			}
			printf ("%d+", s.top());
			s.pop();
		}
	}
	return 0;
}

祝大家 Noip rp++

也希望我以后能更努力一些，加油!