Codeforces 538B Quasi Binary：貪心分解為最少準二進制數

題目描述

準二進制數：十進制只含 0 和 1（如 101, 110011）。給定 n (≤ 1e6)，將其分解為最少個數的準二進制數之和，輸出個數及任意一組分解。

貪心策略

每一位數字 d 需要 d 個準二進制數在該位貢獻 1。因此最少個數 = n 的十進制各位最大值 k = max(digit)。構造方法：對每個準二進制數 j=1..k，其第 i 位為 1 當 digit[i] ≥ j，否則 0。

示例

n = 32，位數 [3,2]，最大值 3。
構造：
j=1：兩位都 ≥1 → 11
j=2：兩位都 ≥2 → 11
j=3：十位 ≥3，個位 <3 → 10
和：11+11+10=32。

C++ 代碼實現

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

int main() {
    int n; cin >> n;
    string s = to_string(n);
    int k = 0;
    for (char c : s) k = max(k, c - '0');
    vector ans(k, 0);
    int len = s.size();
    for (int i = 0; i < len; ++i) {
        int d = s[i] - '0';
        int place = 1;
        for (int j = len - 1 - i; j > 0; --j) place *= 10;
        for (int j = 0; j < d; ++j)
            ans[j] += place;
    }
    cout << k << endl;
    for (int x : ans) cout << x << " ";
    cout << endl;
    return 0;
}

複雜度

• 時間：O(log n × k) ≤ O(6 × 9) = O(1)。
• 空間：O(k)。