[HNOI2006] 鬼谷子的钱袋

传送门：$>here<$

---

题意：求最少将$n$分解成几个数，使得他们能组合出$n$以内的所有数。并且需要满足只有数值$1$能够重复。

数据范围：$n leq 1e9$

---

$Solution$

如果可以有重复数字，那么直接对原数进行二进制拆分，此时会留下一个数$x$。我们证明直接把$x$放着就好了：显然前面部分可以组成连续值域$[0,sum]$，那么$>sum$的部分一定可以通过$x+$之前值域内某个数凑出。

现在考虑不能重复。假设$x$与$k$重复，那么我们令$k--$,$x++$。证明：$k--$之后前面部分的值域变为$[0,sum-1]$，后面部分依然同理。证毕。

$my code$

/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 20010;
const int INF = 1061109567;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
    int x = 0; int w = 1; register char c = getchar();
    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
    if(c == '-') w = -1, c = getchar();
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
int M,rem,tot,N;
int ans[500010];
int main(){
    M = read();
    for(int i = 1; ; i *= 2){
        if(N + i <= M){
            ans[++tot] = i;
            N += i;
        }
        else break;
    }
    if(N < M){
        ans[++tot] = M-N;
    }
    if(M-N > 1){
        for(int i = 2; i < tot; ++i){
            if(M-N == ans[i]){
                ans[i]--;
                ans[tot]++;
                break;
            }
        }    
    }
    sort(ans+1,ans+tot+1);
    printf("%d
", tot);
    for(int i = 1; i <= tot; ++i) printf("%d ", ans[i]);
    return 0;
}