Quasi Binary

题目大意

就是给你一个数 ,然后你要把 表示成看上去像二进制的十进制数的和,要求这样的数越少越好

分析

对于一个十进制数 ,可以表示为
那么这个可以作为其中一些不是最优的解,那么我们考虑优化一下上面的这个东西
根据乘法分配律,对于前面那个东西相同的部分是可以合并的,那么就可以变成
那么更显然的是啥呢,就是所有的 都是一定不同的,所以可以直接把小的部分合并到大的部分中,其中这并不会产生进位,就是说最后不会影响答案的正确性,那么最后的答案就是
那么就是可以枚举每一位,令第 的大小为 ,那么就可以随机找 个将要输出的值加上 即可。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int ans[10], len;

int main()
{
    int x = __read();
    for (int i = 1; i <= x; i *= 10) {
        int temp = x / i % 10;
        len = max(len, temp);
        for (int j = 1; j <= temp; ++j) ans[j] += i;
    }
    printf ("%d\n", len);
    for (int i = 1; i <= len; ++i) printf("%d\n", ans[i]);
    puts("");
}