题解 P1755 【斐波那契的拆分】

· · 题解

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

众所周知 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++

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