CodeForces - 225B：Well-known Numbers（打表，贪心）

53 阅读 0 评论 35 点赞

我是靠谱客的博主丰富小丸子，最近开发中收集的这篇文章主要介绍CodeForces - 225B：Well-known Numbers（打表，贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Discription
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.

Examples
Input
5 2
Output
3
0 2 3
Input
21 5
Output
3
4 1 16

题意
定义f(k,n)为类似菲波那契数推导，只不过变为前k项的和，然后给出一个数s，利用k-菲波那契数构造出一个不重复的集合的元素和为s，集合的规模大于1。输出任意一种情况即可，不需要按顺序。

思路
先将数列打表，大约50位即可，然后倒序查找，小于s则存到一个vector中，sum+1，s-去当前值，直到s为0为止，输出即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
long long a[1000001];
int s,k,sum;
vector<long long>v;
void yu()//预处理，打表
{
a[0]=1;
a[1]=1;
sum=1;
for(int i=2;i<50;i++)
{
if(i-1-k>=0)
a[i]=2*a[i-1]-a[i-k-1];//根据3推出的公式
else
{
for(int j=max(0,i-k);j<=i-1;j++)
a[i]+=a[j];//i-1<k时
}
}
//for(int i=1;i<50;i++) cout<<a[i]<<endl;
}
void go()//贪心查找过程
{
for(int i=50;i>=1;i--)
{
if(s==0)
break;
else if(a[i]<=s&&a[i]>=0&&a[i]<=1e9)
{
v.push_back(a[i]);
s-=a[i];
//cout<<"***"<<endl;
}
//cout<<"***"<<endl;
}
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
return;
}
int main()
{
cin>>s>>k;
yu();
go();
return 0;
}