CodeForces - 225B题解

知识：无
题目：CodeForces - 225B链接

Numbers k-bonacci (k is integer, k > 1) are a generalization of Fibonacci numbers and are determined as follows:
- F(k, n) = 0, for integer n, 1 ≤ n < k;
- F(k, k) = 1;
- F(k, n) = F(k, n - 1) + F(k, n - 2) + … + F(k, n - k), for integer n, n > k.
Note that we determine the k-bonacci numbers, F(k, n), only for integer values of n and k.You’ve got a number s, represent it as a sum of several (at least two) distinct k-bonacci numbers.
Input
The first line contains two integers s and k (1 ≤ s, k ≤ 109; k > 1).
Output
In the first line print an integer m (m ≥ 2) that shows how many numbers are in the found representation. In the second line print m distinct integers a1, a2, …, am. Each printed integer should be a k-bonacci number. The sum of printed integers must equal s.
It is guaranteed that the answer exists. If there are several possible answers, print any of them.
Example
Input
5 2
Output
3
0 2 3
Input
21 5
Output
3
4 1 16

题意：题目中介绍了一个与斐波那契数列相识的k-bonacci数列。斐波那契数列是第一二项为1，从第三项开始，每一项等于前两项之和。而题中k-bonacci数列是前k-1项=0；第k项=1；从第k+1项开始，每一项等于前k项之和。现在给你s，s是由两个以上不同的k-bonacci数加和而成，当然k会给出。问你加和成s的k-bonacci数是那些？输出个数，并且输出这些k-bonacci数。（有多组的话，只需随便输出一组）
思路：这道题的思路很简单，打表然后贪心，但是其中有一些坑需要注意（PS：看完思路后尽量自己先去做一下，实在想不到再看具体方法解析）
方法：

1. 打表，这个地方有坑，不能完全按照题意暴力，题意反复相加会导致不必要的运算，无谓增加时间复杂度，就会Time Limit。也不能完全按照题意打表，把那些0都放数组里，题里给k最大可以达到10^9;数组存不下，就会Runtime error。其实很简单，用一个 变量sum代表前i-1项的和，sum-=第i-1-k项不就是第 i 项的值吗。
2. 贪心求解就直接用s去减表中k-bonacci数（必须减完后>=0的数才能减），可以减的话就用数组记录一下，直到s==0结束；
   PS:斐波那契数列： 0、1、1、2、3、5、8、13、21、34、……

代码实现：

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int s,k;
int f[maxn];

int t=0;
void k_bonacci()
{
    f[0]=1;int sum = 1;
    for(int i=1;sum<=s;i++){
        f[i]=sum;
        sum+=f[i];
        if(i+1>k) sum-=f[i-k];
        t++;
    }
}

vector<int > vec;
void solve()
{
    int j=t;
    while(s){
        if(s>=f[j]) {
            s-=f[j];
            vec.push_back(f[j]);//cout<<" "<<j<<" "<<f[j]<<endl;
        }
        j--;
    }
    if(vec.size()==1) cout<<2<<endl<<0<<" "<<*vec.begin()<<endl;
    else {
        cout<<vec.size()<<endl;
        for(vector<int >::iterator i=vec.begin();i!=vec.end();i++)
            cout<<*i<<" ";
        cout<<endl;
    } 
}
int main()
{
    cin>>s>>k;
    k_bonacci();
    solve();
    return 0;
}

小结：这道题把我坑到了，无论是刚开始完全不动脑，直接按照题意暴力，竟然把所有0都存进去了，虽然这样代码很好写，还是之后反复加算，无谓增加时间复杂度，把o（n）的算法能写到o（n*k）我也是厉害了，亦或是最后sum<=s 忘写=，竟然查了好长时间没查出来，都很智障。。。（今天codeforces竟然不能看错的样例，很无奈。。。）