CodeForces 225B Well-known Numbers（思维打表+贪心策略）

80 阅读 0 评论 53 点赞

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

概述

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
题目大意：
k-bonacci数列是前k-1项=0；第k项=1；从第k+1项开始，每一项等于前k项之和（k>=2）
问你加和成s的k-bonacci数是那些
有多组的话，只需随便输出一组
思维分析：
比较容易想到的就是暴力打表然后搜索需要的数值
如果无脑直接写的话会发现数据打表处理的时间很容易就爆内存（k最大可以达到10^9）
可能前k-1项全为零，那是不是就可以压缩合并一下？
可不可以直接在打表的时候就直接加和记录？
所以要在搜索之前适当处理一下

#include<iostream>
#include<vector>
using namespace std;
#define maxn 1000005
using namespace std;
int s,k;
int f[maxn];
vector<int > vec;
int t=0;
void k_bonacci()
{
f[0]=1;int sum = 1;
//把那些0都放数组f[0]里，题里给k最大可以达到10^9，防止溢出
for(int i=1;sum<=s;i++){
f[i]=sum;
sum+=f[i];
//两步的含义为 累加和同时赋值
if(i+1>k) sum-=f[i-k]; //核心！！！！保持每一个f[i]都是前k项的加和,
//不怎么容易理解，用一个 变量sum代表前i-1项的和，
//sum-=第i-1-k项就是第 i 项的值
t++;
//因为循环条件内没有加次的统计，在此处放置哨兵统计次数
}
}
void solve()
{
int j=t;
while(s){
if(s>=f[j]) {
s-=f[j];
//贪心策略的实现
vec.push_back(f[j]);
}
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;
}