P2320 [HNOI2006]鬼谷子的钱袋（想法）

原题： https://www.luogu.org/problem/P2320

题意：

给出一个m，你讲起拆分成最少份，使得可以组成1到m之间的任意数，大于1数只能有一份。

解析：

以39为例，按照二进制分可以分成$1,2,4,8,8,16$1,2,4,8,8,16，但是不能出现两个8，怎么改呢？

我们把两个8变成$7$7和$9$9，也就是$1,2,4,7,9,16$1,2,4,7,9,16。

分析对于原来分法的使用：

• 假设没有用8，自然无所谓
• 假设使用了一个8，那么我可以用7和1组成
• 假设使用了一个8和一个1，我可以使用9来代替
• 假设使用了两个8，那么直接用7和9代替

综上所述，此分法的可行性等同于二进制分法，而二进制分法一定是正确的。

代码：

#include<bits/stdc++.h>
using namespace std;

int a[5009];

int main(){
    vector<int>v;
    int n;scanf("%d",&n);
    int p=1;
    while(n){
        v.push_back(p);
        n-=p;
        p=min(2*p,n);
    }
    sort(v.begin(),v.end());
    printf("%d\n",v.size());
    for(int i=0;i<v.size();i++){
        if(v[i]>1&&i!=v.size()-1&&v[i+1]==v[i]){
            printf("%d %d ",v[i]-1,v[i]+1);
            i++;
        }
        else
            printf("%d ",v[i]);
    }printf("\n");
}