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

· · 题解

这道题用到了分治的思想

比如一个数是20，那么我们如何表示从1到20所有的数呢？

脑补一下，11~20和1~10有什么关系？差了个10呗！

那如果我表示6~10呢？只要表示1~5就行了。

同理，3~5可以由1~3来表示，2和3可以用1和2来表示

发现了什么端倪？

表示n以内的任何数字可以用1到n/2内的数字

那么表示n/2以内的任何数字可以用1到n/4以内的数字……

于是便有了本蒟蒻的代码

#include<bits/stdc++.h>
using namespace std;
int m,sum=1,a[100005];
int main()
{
    cin>>m;
    while(m>0)//核心
      {
          m%2==0?a[sum]=m/2:a[sum]=m/2+1;//这一坨等价于if(m%2==0) a[sum]=m/2; else a[sum]=m/2+1;
        m/=2;//分治，防止死循环;
          sum++;
      }
    sum--;//sum会多出1
    sort(a+1,a+sum+1);//排序
    cout<<sum<<endl;
    for(int i=1;i<=sum;i++)
      cout<<a[i]<<" ";  //愉快输出
    return 0;
}