P2320 [HNOI2006]鬼谷子的钱袋

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

此题主要有两种方法:

一、分治思想

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

同理,再要凑出110,则需要凑出15+一个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<<"\n";
for (int i=k;i;i--) cout<<a[i]<<" "; //数组递减,倒序输出
}

二、二进制拆分

类似多重背包问题的二进制分解思想,2n以内的以内的所有数都可以用20,21,22.......2^(n-1)表示出来,且用的数字最少

例如要表示出23以内的所有数,把23二进制拆分:23=20+21+22+23+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=20+21+22+......+2n+余数,对于m-x(0<x<余数),x一定可以用20+21+22+......+2n表示出来(如果无法表示则说明x>20+21+22+......+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",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]); //如果余数最大
}

最新文章

  1. Yii rbac原理和实践
  2. HYSBZ 2957 分块
  3. iOS sqlite3数据库解析
  4. Treap树
  5. 总结——visibility和display
  6. 机器学习 —— 概率图模型(推理:MAP)
  7. 【Tools】maven安装
  8. 关于C#匿名方法
  9. 移动web app开发框架
  10. python调用c代码
  11. java进阶书籍
  12. UVA - 10118 Free Candies 记忆化搜索经典
  13. 网上搜集python面试题(更新中......)
  14. TJOI2010中位数
  15. README.md文件编辑
  16. IIS Asp.Net 访问 Com组件 报拒绝访问
  17. webpack版本兼容性问题错误总结,耽误半天学习
  18. div z-index无论设置多高都不起作用
  19. iOS9UICollectionView自定义布局modifying attributes returned by UICollectionViewFlowLayout without copying them
  20. opencv-python教程学习系列10-颜色空间转换

热门文章

  1. Codeforces 1304E. 1-Trees and Queries 代码(LCA 树上两点距离判奇偶)
  2. Typecho的卡哇伊小猫咪小插件(Live2D猫咪插件)
  3. 使用win10 IIS 发布局域网网站
  4. python package install error and little code bugs
  5. Echart的使用legend遇到的问题小记
  6. nginx配置长连接(ajax60秒请求超时)
  7. RN开发-JSX基础语法
  8. for循环与闭包
  9. SpringBoot学习- 9、Slf4j日志
  10. poj1321棋盘问题(dfs+摆放问题)