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

我们坚信：暴力出奇迹！

这题其实打一个暴力就能过，具体思路是先把斐波那契数列的前45项求出来（只要大于10^9就行了，弄个五的倍数吉利~QAQ~）

斐波那契数列求出来了后，进行一个贪心（当前最大可选那个），从后面大的数据开始算（原题：若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组）

贪心过后，把答案存在一个数组里，逆序输出。

代码如下（纯净代码）

#include<bits/stdc++.h> //懒人专用，但比赛可能会爆ling。
using namespace std;
long long a[45];
void fen(int x)
{
    cout<<x<<"=";
    int q[45],w=0;
    memset(q,0,sizeof(q));//个人习惯
    int k=x;
    while(k>0)
    {
        int l=45-1;
        while(a[l]>k&&l>=0) l--;
        q[w]=a[l];
        w++;
        k-=a[l];
    }
    cout<<q[w-1];//格式输出
    for(int i=w-2;i>=0;i--) cout<<"+"<<q[i];
    cout<<endl;//洛谷识别不出/n
}
int main()
{
    a[0]=a[1]=1;
    for(int i=2;i<45;i++) a[i]=a[i-1]+a[i-2];
    //构造数列
    int t,n;
    cin>>t;
    while(t--) 
    {
        cin>>n;
        fen(n);//自动忽略函数名T_T
    }
    return 0;
}

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

原文：https://www.cnblogs.com/oierscw/p/12542193.html