自动搬运

查看原文

来自洛谷，原作者为

	安笙凉城 **

搬运于2025-08-24 21:36:20，当前版本为作者最后更新于2017-11-05 23:24:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

#这道题用到了分治的思想

##比如一个数是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;
}