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

P2320 [HNOI2006]鬼谷子的钱袋

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

此题主要有两种方法：

一、分治思想

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

同理，再要凑出1_{10，则需要凑出1}5+一个5元的钱袋

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

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

#include<iostream>
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<<"
";
	for (int i=k;i;i--) cout<<a[i]<<" "; //数组递减，倒序输出
}

二、二进制拆分

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

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

也许你会问：1,2,4,8以二进制的方式可以凑出1_{15，但是16}22之间的数就一定能用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⁰⁺²1+2^2+......+2n+余数，对于m-x（0<x<余数），x一定可以用2⁰⁺²1+2^2+......+2n表示出来（如果无法表示则说明x>2⁰⁺²1+2^2+......+2n即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<cstdio>
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-(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]); //如果余数最大
}