luogu2320 鬼谷子的钱袋 题目大意 题解
鬼谷子决定将自己的金币数好并用一个个的小钱袋装好，以便在他现有金币的支付能力下，任何数目的金币他都能用这些封闭好的小钱的组合来付账。求钱袋数最少，并且不有两个钱袋装有相同的大于1的金币数的装钱袋方法。
题解
做了这道题相当于长了一点经验。我们的结论是：$lceil frac{n}{2} ceil$和能凑成$[1,lfloor frac{n}{2} floor]$的数字们能凑成$[1,n]$内的所有数字。这样我们就可以/2递推解决了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int a[50];
int cnt = 0;
while(n)
{
a[++cnt] = (n + 1) / 2;
n /= 2;
}
printf("%d
", cnt);
for (int i = cnt; i >= 1; i--)
printf("%d ", a[i]);
printf("
");
return 0;
}