[洛谷 2320][HNOI2006]鬼谷子的钱袋

题目链接

https://www.luogu.org/problemnew/show/P2320

题解

这道题第一问显然有些二进制的味道啊,比如说我们想要组成7的话:

001

010

100

这么加起来不就能组成7了吗!(真的是小学奥数)

上面的这三个数字不仅能组成7,甚至还能组成1-7的所有数字(这不是废话嘛)

于是答案是3,而7的二进制位数也是3。

这时肯定有人要提出疑问了,假如是8呢?

那么应该这样:

001

001

010

100

结果需要4个钱袋,而8的二进制位数为4。

于是我们的答案就推出来了,就是\( \log_2 m +1\)(说白了,就是m的二进制位数)。

至于第二问嘛,让我们重新分析一下上面的过程。

当\(m=7\)时,首先必须有1,然后为了节省数字,我们肯定需要\(m/2\)的数字(二分法了解一下,上面解第一问的过程就是基于二分的原理),于是就有了4和2。

所以需要的数字就是1、2、4了,这样的推理方法和上面得到了一样的结果,同时,第二问的解法也同时水落石出了。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a[105];
int main()
{
 int m,cnt=0;
 scanf("%d",&m);
 printf("%d\n",(int)log2(m)+1);
 while(m>0)
 {
  if(m%2)a[++cnt]=m/2+1;
  else a[++cnt]=m/2;
  m/=2;
 }
 sort(a+1,a+cnt+1);
 for(int i=1;i<=cnt;i++)
  printf("%d ",a[i]);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注