20054 题解【[HNOI2006]鬼谷子的钱袋】

P2320 [HNOI2006]鬼谷子的钱袋

挺有趣的一道题，之所以发这篇题解是因为感觉思路的更清晰一点qwq

此题主要有两种方法：

一、分治思想

例如要凑出120，假如我们已经能凑出110了，那么只要再有一个10元的钱袋，便可以凑出11~20

同理，再要凑出110，则需要凑出15+一个5元的钱袋

就这样不断分治，那么每次n/2都是一定会选的数

如果n是奇数，如21，那么只要凑出1~10加上一个11元的钱袋即可

#include
using namespace std;
int m,k,a[31]; //2^30>10^9
int main(){
    cin>>m;
    while(m) a[++k]=(m+1)/2,m/=2; //每次m/2都是一定会选的数
    cout<<k<<"\n";
    for (int i=k;i;i--) cout<<a[i]<<" "; //数组递减，倒序输出
}

二、二进制拆分

类似多重背包问题的二进制分解思想，2^n以内的以内的所有数都可以用2^0，2^1，2^2.......2^（n-1）表示出来，且用的数字最少

例如要表示出23以内的所有数，把23二进制拆分：23=2^0+2^1+2^2+2^3+8=1+2+4+8+8（最后的8是拆分后的余数），也就是用1,2,4,8,8可以凑出1~23。

也许你会问：1,2,4,8以二进制的方式可以凑出115，但是1622之间的数就一定能用1,2,4,8,8凑出来吗？

其实16~22中的任一个数都可以表示成23-x（0<x<8）的形式，而对于0<x<8是一定可以用1,2,4,8凑出的,实际上就是从1,2,4,8,8中去掉几个钱袋而已。

同理，如果要表示出m以内的数：拆分m=2^0+2^1+2^2+......+2^n+余数，对于m-x（02^0+2^1+2^2+......+2^n即x>=2^(n+1）,那么x还可以继续拆分，与题意不符）

此外还要注意不得有两个钱袋装有相同的大于1的金币，对于23中的两个8，可以改为7,9（由于凑出数时1是肯定要用上的，当我们需要用8时，直接用7+1就可以，如果还需要1，7+1+1，直接用9就好了，当然最好还是有special judge）。由于2^n是递增的，所以最多是余数与一个数相同，特判即可，不需排序。

代码长了一些主要是因为特判，然而似乎比分治稍微快一点qwq？

#include
using namespace std;
int m,n,a[31];
bool flag; //是否有余数？
int main() {
    scanf("%d",&m);
    for (int x=1; x<=m; x<<=1)
        a[++n]=x,m-=x; //二进制拆分
    n++;
    if (m) a[n]=m; //余数
        else flag=1; 
    printf("%d\n",n-(flag==1)); //没有余数就-1
    for (int i=1; i<n; i++) {
        if (!flag) { //如果余数还没输出，则判断当前位置是否该输出余数了
            if (a[i]==a[n]) printf("%d ",a[n]-1),a[i]++,flag=1; //余数与一个数相同
            else if (a[n]<a[i]) printf("%d ",a[n]),flag=1; //没有数与余数相同，按顺序输出
        }
        printf("%d ",a[i]);
    }
    if (!flag) printf("%d",a[n]); //如果余数最大
}