2024 小木棍 · 方案二预处理最小数字表

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1635 字

先打出每种根数对应的最小数字

2024
贪心

正文

// CSP-J 2024 复赛 T3 · 小木棍（方案二）
// 原题：https://oj.yecheng.tv/p/ccf-CSPJ2024C
//
// 方案二 · 预处理「花 c 根能拼出的最小数字」
// 方案一每一位都要把 0 到 9 试一遍。其实同一根数下哪个数字最小是固定的，
// 可以先打成两张表：
//   花 2 根 -> 1     花 3 根 -> 7     花 4 根 -> 4
//   花 5 根 -> 2     花 6 根 -> 0     花 7 根 -> 8
//   另外准备一份「不含 0」的版本给首位用（花 6 根时首位只能选 6，不能选 0）。
// 于是每一位只要算出「这一位允许花几根」的区间，再在表里取最小值就行：
//   剩下 left 位时，这一位最少要花 rest - 7 * left 根、最多花 rest - 2 * left 根，
//   再和 [2, 7] 取交集即可。整体 O(len)，比方案一少一个 10 倍常数。

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

int match[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
// minDigit[c]：正好花 c 根时能拼出的最小数字（可以是 0）
int minDigit[8] = {0, 0, 1, 7, 4, 2, 0, 8};
// minDigitNz[c]：同上但不能是 0，给首位用
int minDigitNz[8] = {0, 0, 1, 7, 4, 2, 6, 8};

int main() {
    freopen("sticks.in", "r", stdin);
    freopen("sticks.out", "w", stdout);

    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;

        int len = (int)((n + 6) / 7);
        if (len < 1) len = 1;
        if (2LL * len > n) {
            cout << -1 << "\n";
            continue;
        }

        long long rest = n;
        string ans;
        for (int i = 0; i < len; i++) {
            long long left = len - i - 1;
            long long a = max(2LL, rest - 7LL * left);     // 这一位最少花几根
            long long b = min(7LL, rest - 2LL * left);     // 最多花几根
            int best = 10;
            for (long long c = a; c <= b; c++) {
                int d = (i == 0 ? minDigitNz[c] : minDigit[c]);
                best = min(best, d);
            }
            ans += char('0' + best);
            rest -= match[best];
        }
        cout << ans << "\n";
    }
    return 0;
}

2024 小木棍 · 方案二 预处理最小数字表

正文

CSP-J 标程 · 复赛真题的其它内容

2024 小木棍 · 方案二预处理最小数字表