CF225B Well-known Numbers（数学+贪心）

怎么感觉自己啥题都想不出来了呢orz
我们只需要处理出<=1e9的每一项，我们发现对于k>=31，就是只有30项，1…2^29,因为2^30>1e9.对于k<31，我们可以直接求一下每一项，打表发现最多43个不同的数字（不算0）。然后贪心的每次减掉能减掉的最大的序列中的数即可。
至于为啥，脑补一下，我们发现 2fi>=fi+1 2 f i >= f i + 1 ，所以做到第i位时，一定有 s<2fi s < 2 f i
一定不会有相同的数出现，然后大概所有正整数都可以分解成若干个k-bonacci数的和，我也不是很会证为啥，不过脑补一下大概很有道理。
Visjiao巨佬简单的用归纳证了一下orz：portal

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
inline char gc(){
static char buf[1<<16],*S,*T;
if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T) return EOF;}
return *S++;
}
inline ll read(){
ll x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int s,k,a[100],bin[31],n,ans[100],m=0;
int main(){
//
freopen("a.in","r",stdin);
s=read();k=read();bin[0]=1;
for(int i=1;i<=30;++i) bin[i]=bin[i-1]<<1;
if(k>=31){
for(int i=1;i<=30;++i) a[i]=bin[i-1];n=30;
}else{
for(int i=1;i<=k;++i) a[i]=bin[i-1];int sum=bin[k]-1;n=k;
while(1){
if(sum>1e9) break;++n;a[n]=sum;sum+=a[n]-a[n-k];
}
}while(1){
if(s>=a[n]) ans[++m]=a[n],s-=a[n];if(!s&&m>1) break;--n;
}printf("%dn",m);
for(int i=1;i<=m;++i) printf("%d ",ans[i]);
return 0;
}

最后

以上就是傲娇巨人为你收集整理的CF225B Well-known Numbers（数学+贪心）的全部内容，希望文章能够帮你解决CF225B Well-known Numbers（数学+贪心）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。