Codeforces 225B Wellknown Numbers

http://codeforces.com/problemset/problem/225/B

思路：维护一个长度为k的队列，利用第k个k-bonacci数等于前面k个k-bonacci数的和，求出所有不大于s的k-bonacci数，可以用一个set来记录，然后每次贪最接近s的数。

View Code

 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <iostream>
 8 #include <cmath>
 9 #include <cstring>
10 #include <algorithm>
11 #include <string>
12 #include <vector>
13 #include <queue>
14 #include <stack>
15 #include <map>
16 #include <set>
17 using namespace std;
18 
19 typedef long long ll;
20 const int INF = 2147483647;
21 
22 set<int>su;
23 void cal(int s,int k)
24 {
25     queue<int>q;
26     q.push(1);
27     int sum=1;
28     su.insert(sum);
29     ll tmp;
30     while(1)
31     {
32         if(q.size() == k)
33         {
34             su.insert(sum);
35             tmp = (ll)(2*sum )- q.front();
36             if(tmp > s)return;
37             su.insert(tmp);
38             q.push(sum);
39             sum = tmp;
40             q.pop();
41         }
42         else
43         {
44             su.insert(sum);
45             tmp = (ll)sum * 2;
46             if(tmp > s)return ;
47             q.push(sum);
48             sum = tmp;
49 
50         }
51     }
52     return;
53 }
54 int main()
55 {
56     #ifndef ONLINE_JUDGE
57     freopen("in","r",stdin);
58     #endif
59     int s,k;
60     while(~scanf("%d%d",&s,&k))
61     {
62         cal(s,k);
63         int S[35]={0},top=1;
64         while(s)
65         {
66             set<int>::iterator it = su.lower_bound(s);
67             if(it != su.begin() && *it != s)it--;
68             S[top++]=*it;
69             s-=*it;
70         }
71         printf("%d\n",top);
72         for(int i=top-1;i>=0;i--)printf("%d ",S[i]);
73         puts("");
74     }
75     return 0;
76 }

by Farmer