[CSP-J 2024] 小木棍

题意

给定 $n$ 根小木棍，要拼出一个正整数，满足：

恰好使用 $n$ 根木棍；
没有前导零；
在满足条件的所有正整数中尽可能小。

如果不存在，输出 $-1$ 。

数字需要的木棍数量为：

数字	0	1	2	3	4	5	6	7	8	9
木棍数	6	2	5	5	4	5	6	3	7	6

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65// brute.cpp：小数据 DP，保存每个火柴数能拼出的最小字符串。
#include <bits/stdc++.h>
using namespace std;

int cost_digit[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

bool better(const string &a, const string &b) {
    if (a.empty()) {
        return false;
    }
    if (b.empty()) {
        return true;
    }
    if (a.size() != b.size()) {
        return a.size() < b.size();
    }
    return a < b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

        vector<string> dp(n + 1, "");
        for (int d = 1; d <= 9; d++) {
            if (cost_digit[d] <= n) {
                string s = "";
                s += char('0' + d);
                if (better(s, dp[cost_digit[d]])) {
                    dp[cost_digit[d]] = s;
                }
            }
        }

        for (int sum = 0; sum <= n; sum++) {
            if (dp[sum].empty()) {
                continue;
            }
            for (int d = 0; d <= 9; d++) {
                int next_sum = sum + cost_digit[d];
                if (next_sum > n) {
                    continue;
                }
                string s = dp[sum] + char('0' + d);
                if (better(s, dp[next_sum])) {
                    dp[next_sum] = s;
                }
            }
        }

        if (dp[n].empty()) {
            cout << -1 << '\n';
        } else {
            cout << dp[n] << '\n';
        }
    }

    return 0;
}

下面是另一种「按位构造」写法。它从左到右决定每一位放哪个数字，并用剩余木棍数判断后续是否还能填满：

另一种写法：按位构造

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// brute_01_style.cpp：按位构造写法，把每一位放哪个数字看成一层决策。
#include <bits/stdc++.h>
using namespace std;

int cost_digit[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int total_len;
string answer;

// 判断剩余 rest 根火柴能否填满 slots 个数位。
bool can_fill(int rest, int slots) {
    if (rest < 0) {
        return false;
    }
    return 2 * slots <= rest && rest <= 7 * slots;
}

bool dfs_build(int pos, int rest) {
    if (pos == total_len) {
        return rest == 0;
    }

    int slots_left = total_len - pos - 1;
    int start_digit = (pos == 0 ? 1 : 0);

    // 从小到大尝试数字，第一次成功就是当前长度下的最小数。
    for (int d = start_digit; d <= 9; d++) {
        int left = rest - cost_digit[d];
        if (!can_fill(left, slots_left)) {
            continue;
        }
        answer[pos] = char('0' + d);
        if (dfs_build(pos + 1, left)) {
            return true;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

        if (n == 1) {
            cout << -1 << '\n';
            continue;
        }

        total_len = (n + 6) / 7; // 位数越少，正整数越小。
        answer.assign(total_len, '0');

        if (dfs_build(0, n)) {
            cout << answer << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

brute.cpp 用 DP 保存每个木棍数能拼出的最小字符串，适合小数据验证，但 $n$ 到 $10^5$ 时不能保存和比较大量长字符串。

要让正整数尽可能小，第一优先级是位数尽可能少。因为任意 $L$ 位正整数都小于任意 $L+1$ 位正整数。一个数字最多消耗 $7$ 根木棍，所以最少位数是 $len = \lceil n/7 \rceil$ 。 $n = 1$ 时没有任何数字能用一根木棍拼出，输出 $-1$ 。

$len$ 位一定能拼出吗？ 由于数字 $1,7,4,2,3,5,6,0,9,8$ 的木棍消耗分别为 $2,3,4,5,5,5,6,6,6,7$ ，即 $2..7$ 每种消耗都存在对应数字（首位不能用 $0$ ，但 $1,7,4,2,3,5,6,8,9$ 同样覆盖 $2..7$ ）。因此对于 $len$ 位数字，能达到的木棍总数范围是 $[2 \cdot len,\, 7 \cdot len]$ ，且这个区间的每个整数都能通过微调某一位实现（把某位的数字换成多 $1$ 根木棍的即可）。

对于 $len = \lceil n/7 \rceil$ ，显然 $n \leqslant 7 \cdot len$ 。还需验证 $n \geqslant 2 \cdot len$ ：由 $\lceil n/7 \rceil = len$ 知 $n > 7(len-1)$ ，即 $n \geqslant 7(len-1)+1 = 7 \cdot len - 6$ 。当 $len \geqslant 2$ 时， $7 \cdot len - 6 \geqslant 2 \cdot len$ 等价于 $5 \cdot len \geqslant 6$ ，成立。 $len = 1$ 时 $n \in [2, 7]$ ，也在 $[2, 7]$ 范围内。因此 $n$ 必然落在可达区间内， $len$ 位数一定可以拼出。

确定了最少位数后，以下是两种实现方式。

解法一：贪心（逐位构造）

从高位到低位逐位决定数字。每位的选择规则：

第一位不能选 $0$ ，后面的位可以选 $0$ ；
从小到大尝试数字，选中后剩余的木棍数必须能被剩余位数填满。

由于每位最少用 $2$ 根、最多用 $7$ 根，且 $2..7$ 每种消耗都存在对应数字，剩余 $slots$ 位、剩余 $rest$ 根时的可行条件是：

text

12 * slots <= rest <= 7 * slots

于是每一位从小到大枚举数字，找到第一个满足条件的即可。

样例理解

$n = 18$ 时，最少位数是 $\lceil 18/7 \rceil = 3$ 。

第一位尝试 $1$ ，用掉 $2$ 根，剩 $16$ 根给 $2$ 位，超过 $2 \times 7 = 14$ ，不可行；
第一位尝试 $2$ ，用掉 $5$ 根，剩 $13$ 根给 $2$ 位，可行；
第二位尽量小，选 $0$ 后剩 $7$ 根给最后一位，可行；
最后一位只能选 $8$ 。答案是 $208$ 。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include <bits/stdc++.h>
using namespace std;

int cost_digit[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

bool can_fill(int rest, int slots) {
    return 2 * slots <= rest && rest <= 7 * slots;
}

char choose_digit(int rest, int slots, bool first_digit) {
    int start = first_digit ? 1 : 0;
    for (int d = start; d <= 9; d++) {
        int left = rest - cost_digit[d];
        if (can_fill(left, slots - 1)) {
            return char('0' + d);
        }
    }
    return '?';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

        if (n == 1) {
            cout << -1 << '\n';
            continue;
        }

        int len = (n + 6) / 7; // 位数越少，正整数越小
        int rest = n;

        for (int pos = 1; pos <= len; pos++) {
            char ch = choose_digit(rest, len - pos + 1, pos == 1);
            cout << ch;
            rest -= cost_digit[ch - '0'];
        }
        cout << '\n';
    }

    return 0;
}

解法二：DP 预处理

如果不习惯用 $can_fill$ 做区间可行性判断，也可以把每个木棍数的最优方案提前 DP 算出来，查询时直接查表输出。

核心思想：对于木棍数 $i$ ，记录最优方案的位数和首数字。更优标准：位数越少越好，位数相同时首数字越小越好。

text

1
2best_0[i]：i 根木棍的最优方案（允许首数字为 0，用于非首位）
best_1[i]：i 根木棍的最优方案（不允许首数字为 0，用于第一位）

预处理时对每个 $i$ （ $2..\textit{MAXN}$ ），枚举首数字 $d$ （ $best_1$ 从 $1$ 开始， $best_0$ 从 $0$ 开始）。用掉 $stick[d]$ 根后剩余 $rest$ ，如果 $rest == 1$ 跳过（ $1$ 根无法拼数字），否则总位数为 $best_0[rest].len + 1$ ，选最优者。

查询时：输出 $best_1[n].digit$ ，然后循环用 $best_0[rest]$ 递推输出剩余位。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * date: 2026-07-07 00:00:00
 */
// main_dp.cpp：DP 预处理每个木棍数的最优(位数,首数字)，O(N*10) 预处理 + O(1) 查询。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int stick[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

// best_len_0[i] / best_digit_0[i]：i 根木棍的最优方案（允许首数字为 0，用于非首位）
int best_len_0[MAXN], best_digit_0[MAXN];
// best_len_1[i] / best_digit_1[i]：i 根木棍的最优方案（不允许首数字为 0，用于第一位）
int best_len_1[MAXN], best_digit_1[MAXN];

// 比较 (len_a, digit_a) 是否优于 (len_b, digit_b)
// 更优：位数更少，或位数相同且首数字更小
bool better(int len_a, int digit_a, int len_b, int digit_b) {
    if (len_a == 0) return false; // 当前状态无效
    if (len_b == 0) return true;  // 被比较状态无效
    if (len_a != len_b) return len_a < len_b;
    return digit_a < digit_b;
}

void precompute() {
    for (int i = 2; i < MAXN; i++) {
        // 填 best_0：首数字允许为 0
        for (int d = 0; d <= 9; d++) {
            int cost = stick[d];
            if (i < cost) continue;
            int rest = i - cost;
            if (rest == 1) continue; // 剩余 1 根无法拼出任何数字
            int cand_len = (rest == 0) ? 1 : best_len_0[rest] + 1;
            int cand_digit = d;
            if (better(cand_len, cand_digit, best_len_0[i], best_digit_0[i])) {
                best_len_0[i] = cand_len;
                best_digit_0[i] = cand_digit;
            }
        }

        // 填 best_1：首数字不允许为 0
        for (int d = 1; d <= 9; d++) {
            int cost = stick[d];
            if (i < cost) continue;
            int rest = i - cost;
            if (rest == 1) continue;
            int cand_len = (rest == 0) ? 1 : best_len_0[rest] + 1;
            int cand_digit = d;
            if (better(cand_len, cand_digit, best_len_1[i], best_digit_1[i])) {
                best_len_1[i] = cand_len;
                best_digit_1[i] = cand_digit;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n == 1 || best_len_1[n] == 0) {
            cout << -1 << '\n';
            continue;
        }
        // 输出第一位（由 best_1 确定），剩余用 best_0 递推
        int cur = n;
        cout << best_digit_1[cur];
        cur -= stick[best_digit_1[cur]];
        while (cur > 0) {
            cout << best_digit_0[cur];
            cur -= stick[best_digit_0[cur]];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

解法一： $O(位数 \times 10)$ 每次查询， $O(1)$ 空间
解法二：预处理 $O(N \times 10)$ ，查询 $O(位数)$ ， $O(N)$ 空间

总结

本题的贪心顺序是：先保证位数最短，再保证字典序最小。解法一的区间条件 $2 \cdot slots \leqslant rest \leqslant 7 \cdot slots$ 和解法二的 DP 填表本质是两种不同的表达方式，殊途同归。

测试点编号	$n\leq$	特殊性质
$1$	$20$	无
$2$	$50$	^
$3$	$10^3$	A
$4,5$	$10^5$	^
$6$	$10^3$	B
$7,8$	$10^5$	^
$9$	$10^3$	无
$10$	$10^5$	^

目录

题意

思路

解法一：贪心（逐位构造）

样例理解

解法二：DP 预处理

复杂度

总结