10.16 CF538B Quasi Binary

题意简述

给出一个数 $n$ ，你需要将 $n$ 写成若干个数的和，其中每个数的十进制表示中仅包含 $0$ 和 $1$ 。

问最少需要多少个数

题解

考虑一个整数 $n$ ，设 $n = \sum\limits_{i=1}^{k}{a_i\times10^{i-1}}$

容易发现，第 $i$ 位上的数字就是 $a_i$ 。

因为我们分解出来的数里面只能是 $0,1$ ，那么想要得到第 $i$ 位则需要 $a_i$ 个数在该为上有 $1$

因此，输出的第一行就是 $\max\limits_{i=1}^{k} \{a_i \}$

下面考虑构造方案，设 $p_j(j\in\max\limits_{i=1}^{k} \{a_i \})$ 为构造出的第 $j$ 个数，如果 $j \le a_i$ ，则 $j$ 的第 $i$ 位为 $1$ ，否则为零。

代码

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

template < typename Tp >
inline void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

template < typename Tp >
inline void biread(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 2 + ch - '0', ch = getchar();
    x *= fh;
}

int n;
int a[10], cnt;
int ans[10];
inline void Init(void) {
    read(n);
}

inline void Work(void) {
    int t = n;
    while(t) {
        a[++cnt] = t % 10;
        t /= 10;
    }
    int r = 0;
    for(int i = 1; i <= cnt; i++) {
        r = max(a[i], r);
    }
    printf("%d\n", r);
    for(int i = cnt; i >= 1; i--) {
        for(int j = 1; j <= r; j++) ans[j] = ans[j] * 10;
        for(int j = 1; j <= a[i]; j++) {
            ans[j] = ans[j] + 1;
        }
    }
    for(int i = 1; i <= r; i++) {
        printf("%d%c", ans[i], " \n"[i == r]);
    }
}

signed main(void) {
    Init();
    Work();
    return 0;
}