[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

解法总览

三个解法共享同一套优先级：先保证位数最短，再保证字典序最小。由此先定下答案位数 $len = \lceil n/7 \rceil$ ：

单个数字最多消耗 $7$ 根（就是 8）， $m$ 位最多用 $7m$ 根，所以 $m \geqslant \lceil n/7 \rceil$ ；
$len$ 位的总消耗能取到 $[2 \cdot len,\ 7 \cdot len]$ 里每个整数：从全放 1（ $2 \cdot len$ 根）出发，任选一位换成多耗 $1$ 根的数字（ $2\to3\to4\to5\to6\to7$ 每档都有对应数字），一路加到 $7 \cdot len$ ；首位不能放 0，但非零数字 $1,7,4,2,3,5,6,8,9$ 同样覆盖 $2 \sim 7$ 每种消耗，所以每位都能自由加 $1$ ；
因此「 $len$ 位拼得出 $n$ 」的充要条件是 $2 \cdot len \leqslant n \leqslant 7 \cdot len$ 。上界显然成立；下界由 $len = \lceil n/7 \rceil$ 得 $n > 7(len-1)$ ，即 $n \geqslant 7 \cdot len - 6 \geqslant 2 \cdot len$ （ $len \geqslant 2$ 时 $5 \cdot len \geqslant 6$ 成立， $len = 1$ 时 $n \in [2,7]$ 逐个验证）；
边界： $n = 1$ 时连一位都拼不出（每个数字至少 $2$ 根），输出 $-1$ 。

除 $n = 1$ 外答案位数恰为 $len$ ，剩下只差把「字典序最小的 $len$ 位数」填出来。三种做法输入输出格式相同、结论一致，是替代关系：

解法一（main.cpp，正式主解）：打表找规律， $n \leqslant 50$ 直接查 tables[]（由 DFS 暴力预先打好）， $n > 50$ 用「 $r = n \bmod 7$ 决定前缀，再补 8 到 $len$ 位」；
解法二（main_greedy.cpp）：逐位贪心，每位选最小的、能让剩余木棍填满剩余位数的数字；
解法三（main_dp.cpp）：DP 预处理每个木棍数的最优「位数 + 首数字」，查询时直接查表输出。

brute.cpp、brute_01_style.cpp、brute-dfs.cpp、brute-dfs-clip.cpp 是打表和对拍用的朴素解，不参与正式解法。

解法一：找规律（ $n \bmod 7$ 决定前缀）

思路

规律是从打表来的。brute.cpp 用字符串 DP 保存每个木棍数能拼出的最小字符串，适合小数据验证（ $n$ 到 $10^5$ 时不能保存和比较大量长字符串）：

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;
}

另一种更直白的打表方式是 DFS 枚举：dfs(pos, rest) 表示正在决定第 pos 位、还剩 rest 根木棍，每层枚举数字 $0\sim 9$ （首位从 $1$ 开始），到 rest == 0 时把这一整条路径拼成一个数，和当前答案取最小。它没有任何剪枝，只适合很小的 $n$ ，主程序对 $n = 1 \ldots 30$ 打表输出：

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#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll ans;

// 0 1 2 3 4 5 6 7 8 9
ll stick[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
ll rcd[100009];

void dfs(ll pos, ll rest) {
  if (rest == 1) {
    return;
  }
  if (rest == 0) {
    ll num = 0;
    for (ll i = 1; i < pos; i++) num = num * 10 + rcd[i];
    if (ans == -1 || ans > num) ans = num;
    return;
  }

  ll start = 0;
  if (pos == 1) start = 1;

  for (ll i = start; i < 10; i++) {
    if (rest < stick[i]) continue;
    rcd[pos] = i;
    dfs(pos + 1, rest - stick[i]);
  }
}

int main() {

  ll t;
  std::cin >> t;
  // while (t--) {
  //   ll n;
  //   std::cin >> n;
  //
  //   ans = -1;
  //   dfs(1, n);
  //   std::cout << ans << "\n";
  // }

  for (ll i = 1; i <= 30; ++i) {
    n = i;
    ans = -1;
    dfs(1, n);
    std::cout << n << " " << ans << "\n";
  }

  return 0;
}

另一种写法：DFS + 位数剪枝（打表 $n=1 \ldots 50$）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll ans;
ll ans_len;

// 0 1 2 3 4 5 6 7 8 9
ll stick[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
ll rcd[100009];

void dfs(ll pos, ll rest) {

  if (rest == 1) {
    return;
  }
  if (rest == 0) {
    ll num = 0;
    for (ll i = 1; i < pos; i++) num = num * 10 + rcd[i];
    if (ans == -1 || ans > num) {
      ans_len = pos - 1;
      ans = num;
    }
    return;
  }

  // 剪枝
  if (pos > ans_len && ans_len != -1) return;

  ll start = 0;
  if (pos == 1) start = 1;

  for (ll i = 9; i >= start; i--) {
    if (rest < stick[i]) continue;
    rcd[pos] = i;
    dfs(pos + 1, rest - stick[i]);
  }
}

// 1 -1
// 2 1
// 3 7
// 4 4
// 5 2
// 6 6
// 7 8
// 8 10
// 9 18
// 10 22
// 11 20
// 12 28
// 13 68
// 14 88
// 15 108
// 16 188
// 17 200
// 18 208
// 19 288
// 20 688
// 21 888
// 22 1088
// 23 1888
// 24 2008
// 25 2088
// 26 2888
// 27 6888
// 28 8888
// 29 10888
// 30 18888
// 31 20088
// 32 20888
// 33 28888
// 34 68888
// 35 88888
// 36 108888
// 37 188888
// 38 200888
// 39 208888
// 40 288888
// 41 688888
// 42 888888
// 43 1088888
// 44 1888888
// 45 2008888
// 46 2088888
// 47 2888888
// 48 6888888
// 49 8888888
// 50 10888888
// 打表

int main() {

  ll t;
  std::cin >> t;
  // while (t--) {
  //   ll n;
  //   std::cin >> n;
  //
  //   ans = -1;
  //   dfs(1, n);
  //   std::cout << ans << "\n";
  // }

  for (ll i = 1; i <= 50; ++i) {
    n = i;
    ans = -1;
    ans_len = -1;
    dfs(1, n);
    std::cout << n << " " << ans << "\n";
  }

  return 0;
}

从打表结果很容易看出规律： $n = 1$ 输出 $-1$ ，之后答案的位数恰好是 $\lceil n/7 \rceil$ ，并且最优解总是把「费木棍」的数字（如 $8$ ）尽量堆在低位，高位留尽量小的数字。更细一点看， $n$ 是 $7$ 的倍数时答案是一串 8， $n \equiv 1 \pmod 7$ 时答案是 10 后面跟着一串 8——这两类（恰好是数据范围里的特殊性质 A 和 B）有这么干净的规律，那么其他余数应该也各有规律。

省木棍模型：先假设每位都是 `8`

$len$ 位每位都放 8 时共用 $7 \cdot len$ 根，比 $n$ 多出

S = 7 \cdot len - n

根，而且由 $len = \lceil n/7 \rceil$ 知 $0 \leqslant S \leqslant 6$ 。把某一位的 8 换成别的数字，就「省」下一些木棍。各数字相对 8 省下的数量：

数字	0	1	2	3	4	5	6	7	8	9
相对 8 省下	1	5	2	2	3	2	1	4	0	1

于是问题变成： $len$ 位数字（首位非 $0$ ）恰好省下 $S$ 根，且数值尽量小。注意「省得多」和「数字小」并不完全一致（1 省最多却最小，而 0/6/9 只省 $1$ 根），所以不能简单按「省得多的放高位」，而要从高位到低位选尽量小的数字，只要剩下的省法还凑得出剩下的量：当前位选了省 $s$ 根的数字后，剩 $slots$ 位还要省 $S - s$ 根，必须

text

10 <= S - s <= 5 * slots        // 每位最多省 5，最少省 0，中间值都取得到

由于 $S \leqslant 6$ 很小，可以直接把七类余数的答案手推出来，这就是规律。

每个余数对应的前缀

由上文规则，位数足够时从高位往低位贪心放置，得到的是一段固定的前缀，后面全是 8。 $r = n \bmod 7$ 决定要省多少根（ $S = 7 - r$ ），也就决定了前缀：

$r = 0$ （ $S = 0$ ）：不用省，前缀为空，全是 8；
$r = 1$ （ $S = 6$ ）：高位放最小的 1 省 $5$ 根，下一位放 0 再省 $1$ 根凑满，前缀 10；
$r = 2$ （ $S = 5$ ）：1 一位就省够 $5$ 根，前缀 1；
$r = 3$ （ $S = 4$ ）：放 1 会省 $5$ 根超了，改用次小的 2 省 $2$ 根，再用两个 0 各省 $1$ 根凑满 $4$ ，前缀 200；
$r = 4$ （ $S = 3$ ）：2 省 $2$ 根，再放 0 省 $1$ 根，前缀 20；
$r = 5$ （ $S = 2$ ）：2 一位省够，前缀 2；
$r = 6$ （ $S = 1$ ）：首位不能放 0，放省 $1$ 根里最小的 6，前缀 6。

余数 $r$	0	1	2	3	4	5	6
需要省 $S = 7-r$	0	6	5	4	3	2	1
前缀	空	`10`	`1`	`200`	`20`	`2`	`6`

于是位数足够时，答案就是「前缀 + 若干个 8」：先写下 $r$ 对应的前缀，再把 8 补到 $len = \lceil n/7 \rceil$ 位。

上面的推导默认位数足够放下前缀。位数不够的短答案（例如 $r = 3$ 的 $n = 3, 10$ ， $r = 4$ 的 $n = 4$ ）不满足这个前提，由下面的 tables[] 直接覆盖。

样例理解

$n = 18 = 7 \times 2 + 4$ ，属于小数据，查 tables[18] 得 $208$ （恰好也就是 $r = 4$ 的前缀 20 再补一个 8）。规律段取同余数的大数据 $n = 53 = 7 \times 7 + 4$ ： $len = \lceil 53/7 \rceil = 8$ ，前缀 20 加 $6$ 个 8，得 $20888888$ 。

常量表 + 规律： $n \leqslant 50$ 查表， $n > 50$ 套规律

打表不仅能「看」出规律，还可以把打出来的结果保留下来直接用： $n \leqslant 50$ 的答案一共 50 个，提前用上面的 DFS 暴力跑一遍，写成常量数组 tables[]：

cpp

1
2ll tables[] = { -1, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20,
                28, 68, 88, 108, 188, 200, 208, 288, 688, 888, /* ... */ };

tables[] 的数据由独立的 DFS 暴力程序 brute-dfs-clip.cpp 输出，代码里 tables 数组上方的注释也标明了来源。这样两条路径互相独立：小数据完全由暴力背书，大数据靠规律。边界处两者必须吻合： $n = 49$ 是 8888888、 $n = 50$ 是 10888888、 $n = 51$ 是 18888888（ $n = 51$ 已是规律段）。如果某次改错了规律部分， $n = 50$ 和 $n = 51$ 的对比会立刻暴露出来。

$n > 50$ 时 $n/7 \geqslant 7$ ， $len = \lceil n/7 \rceil \geqslant 8$ ，足够放下最长 3 位的前缀，所以规律这条路永远不需要考虑位数不够的情形。

代码

main.cpp 按 $n$ 的大小分流： $n \leqslant 50$ 查 tables[]； $n > 50$ 取前缀再补 8 到 $len$ 位：

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/**
 * 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
 * create_at: 2026-10-02 17:33
 * update_at: 2026-10-03 14:21
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// main.cpp：n <= 50 直接查打表数组 tables[]，n > 50 按 n = 7k + r 的规律输出。
// tables[] 由 brute-dfs-clip.cpp（DFS 暴力打表）生成。

// tables[i]：恰好用 i 根木棍拼出的最小正整数（下标 0 不用，n = 1 无解记为 -1）
// 由 brute-dfs-clip.cpp 的 DFS 暴力打表得到，范围 n = 1..50
ll tables[] = {
    -1,      // n = 0（不用）
    -1,      // n = 1：无解
    1, 7, 4, 2, 6, 8, 10, 18, 22, 20,
    28, 68, 88, 108, 188, 200, 208, 288, 688, 888,
    1088, 1888, 2008, 2088, 2888, 6888, 8888, 10888, 18888, 20088,
    20888, 28888, 68888, 88888, 108888, 188888, 200888, 208888, 288888, 688888,
    888888, 1088888, 1888888, 2008888, 2088888, 2888888, 6888888, 8888888, 10888888,
}; // tables[50] = 10888888

// 规律：n > 50 时答案位数 len = ceil(n/7)，高位放一个固定前缀，其余位全是 8。
// 前缀由 r = n % 7 决定（对应题解的规律表），用字符串直接列出：
//   r = 0 -> ""（全 8），r = 1 -> "10"，r = 2 -> "1"，r = 3 -> "200"，
//   r = 4 -> "20"，r = 5 -> "2"，r = 6 -> "6"。
// n > 50 时 len >= 8，像 r = 3 的 "22"、r = 4 的 "4" 这类位数不够的前缀
// 都已经写在 tables[] 里，走不到这里。
const char* prefix[7] = {"", "10", "1", "200", "20", "2", "6"};

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

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

        if (n <= 50) { // 小数据：直接查打表数组
            cout << tables[n] << '\n';
            continue;
        }

        // 大数据：固定前缀 + 若干 8，补满 len 位
        ll len = (n + 6) / 7; // 答案位数 = ceil(n/7)
        ll r = n % 7;
        ll done = strlen(prefix[r]); // 前缀已经占用的位数
        cout << prefix[r];
        for (ll i = done; i < len; i++)
            cout << '8';
        cout << '\n';
    }

    return 0;
}

复杂度

每次查询 $n \leqslant 50$ 时是 $O(1)$ 查表， $n > 50$ 时 $O(位数)$ ；无预处理， $O(1)$ 空间。

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

思路

规律虽好，但七类分类是「把答案算出来之后」总结的。如果不打表，也可以直接用通用的逐位贪心：从高位到低位逐位决定数字，每位的选择规则是：

第一位不能选 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
49
50
51
52
53
54
55/**
 * 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
 * create_at: 2026-10-02 17:33
 * update_at: 2026-10-02 17:33
 */
#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;
}

复杂度

每次查询 $O(位数 \times 10)$ ，无预处理， $O(1)$ 空间。

解法三：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(N \times 10)$ ，查询 $O(位数)$ ， $O(N)$ 空间。

复杂度对比

解法	预处理	每次查询	空间
解法一：找规律	无	$n \leqslant 50$ 查表 $O(1)$ ， $n > 50$ 时 $O(位数)$	$O(1)$
解法二：贪心	无	$O(位数 \times 10)$	$O(1)$
解法三：DP	$O(N \times 10)$	$O(位数)$	$O(N)$

总结

本题的优先级顺序是：先保证位数最短，再保证字典序最小。解法一把「每位放 8、总共再省 $S = 7 \cdot len - n \leqslant 6$ 根」的构造归纳成「 $r = n \bmod 7$ 决定前缀，其余补 8」，小数据查 tables[]、大数据走前缀；解法二的区间条件 $2 \cdot slots \leqslant rest \leqslant 7 \cdot slots$ 和解法三的 DP 填表，本质是同一个「剩余木棍还能不能填满」判断的不同表达，殊途同归。打表找规律适合赛时抢时间，贪心和 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$	^

目录

形式化题目

解法总览

解法一：找规律（n mod 7n \bmod 7nmod7 决定前缀）

思路

省木棍模型：先假设每位都是 8

每个余数对应的前缀

样例理解

常量表 + 规律：n⩽50n \leqslant 50n⩽50 查表，n>50n > 50n>50 套规律

代码

复杂度

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

思路

样例理解

代码

复杂度

解法三：DP 预处理

思路

代码

复杂度

复杂度对比

总结

解法一：找规律（ $n \bmod 7$ 决定前缀）

省木棍模型：先假设每位都是 `8`

常量表 + 规律： $n \leqslant 50$ 查表， $n > 50$ 套规律