你好！我是你的OI教练。

这道题（CSP-J 2024 T3 小木棍）考察的是 贪心算法 和 数学构造。题目要求拼出的数最小，这通常意味着两个目标：

1. 位数最少（这是决定大小的最关键因素）。
2. 高位数字尽可能小（在位数确定的情况下，字典序最小）。

以下是解题思路提示：

1. 确定位数

首先，我们要让拼出的数字位数最少。 观察给出的数字拼装代价：

• 数字 1：2 根
• 数字 7：3 根
• ...
• 数字 8：7 根

关键点：数字 8 是单个数位能消耗最多木棍的数字（7根）。 为了让位数最少，我们应该尽可能多地填入代价大的数字来快速消耗掉 $n$ 根木棍。 因此，所需的最小位数 $L$ 可以通过简单的除法算出：

$$L = \lceil n / 7 \rceil = (n + 6) / 7 \quad (\text{整数除法}) $$

2. 逐位贪心（构造答案）

在确定了总位数 $L$ 之后，问题就变成了：用 $n$ 根木棍填满 $L$ 个位置，使得生成的数字字典序最小。

我们可以从最高位（第 1 位）开始，一位一位地尝试填入数字 $d$（$0 \sim 9$）：

• 首位限制：第 1 位不能填 0。
• 合法性判断：假设当前位填了数字 $d$（消耗 $c[d]$ 根），那么剩下的木棍数 $n - c[d]$ 必须足够被后面的 $L-1$ 位“消化”掉。
  • 因为每个位置最多只能消耗 7 根木棍（填 8），所以必须满足：$$\text{剩余木棍} \le 7 \times \text{剩余位数}$$
  • 同时，剩余木棍也不能太少，不能少于 $2 \times \text{剩余位数}$（填 1），但在 $n$ 较大时，主要瓶颈是上限。

策略：对于每一位，从小到大枚举数字 $0 \sim 9$（首位从 1 开始），只要填入这个数字后，剩下的木棍数 不大于 后面所有位全填 8 所能消耗的极限，那么这个数字就是当前位能填的最小数字，直接选定它，然后处理下一位。

3. 性能优化

• 如果 $n$ 很大，你会发现一旦开头几位处理完，剩下的木棍数恰好是 $7 \times \text{剩余位数}$ 时，后面的位就全部填 8 了。
• 小数据特判：对于极小的 $n$（比如 $n=1 \sim 10$），贪心策略可能会因为“剩余木棍太少无法填满”的下限问题而出错，或者因为位数计算不准（比如 $n=10$ 时，公式算出来 2 位，但 $2+8=10$ 可以拼出 1 和 ? 吗？不行，10 对应 22 或 40 等）。建议对 $n \le 14$ 左右的情况直接打表或特判，或者在贪心时加上下限判断。

---

标准代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 数字 0-9 对应的木棍数
// 0:6, 1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6
const int costs[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

void solve() {
    int n;
    cin >> n;

    // 特判小数据，防止贪心边界问题
    // 其实 n=1 是无法拼出的
    if (n == 1) {
        cout << -1 << endl;
        return;
    }
    
    // 预处理极小数据的答案（可选，或者依靠下面的逻辑加下限判断）
    // 下面的贪心逻辑配合下限检查其实也能过，但打表更稳
    // 这里列举 n=1~14 的最优解
    // 1:-1
    // 2:1
    // 3:7
    // 4:4
    // 5:2
    // 6:6 (0不行, 6的字典序比9小)
    // 7:8
    // 8:10 (1+0=2+6=8)
    // 9:18 (1+8=2+7=9)
    // 10:22 (2+2=5+5=10, 40=4+6=10. 22小)
    // 11:20 (2+0=5+6=11)
    // 12:28 (2+8=5+7=12)
    // 13:68 (6+8=6+7=13)
    // 14:88 (8+8=7+7=14)
    if (n <= 14) {
        int ans[] = {0, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88};
        cout << ans[n] << endl;
        return;
    }

    // 1. 计算总位数
    // 最多每位消耗7根(8)，所以至少需要 ceil(n/7) 位
    int digits = (n + 6) / 7;

    // 2. 逐位贪心
    for (int i = 1; i <= digits; ++i) {
        // 当前位的尝试范围
        // 如果是首位，不能是0
        int start_d = (i == 1) ? 1 : 0;
        
        for (int d = start_d; d <= 9; ++d) {
            int cost = costs[d];
            
            // 剩余需要的木棍
            int rem_sticks = n - cost;
            // 剩余的位数
            int rem_digits = digits - i;
            
            // 判断可行性：
            // 剩余木棍必须 <= 剩余位数 * 7 (上限，全填8)
            // 剩余木棍必须 >= 剩余位数 * 2 (下限，全填1)
            // 注意：n > 14 时，rem_digits * 2 一般都能满足，主要是上限检查
            if (rem_sticks >= rem_digits * 2 && rem_sticks <= rem_digits * 7) {
                cout << d;
                n -= cost;
                
                // 优化：如果剩余木棍恰好全是8，直接输出
                // 这步不是必须的，但可以加速
                if (rem_digits > 0 && rem_sticks == rem_digits * 7) {
                    for (int k = 0; k < rem_digits; ++k) cout << 8;
                    cout << endl;
                    return;
                }
                break; // 找到最小的 d，填入，跳出数字尝试循环，进入下一位
            }
        }
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

数据生成器

这是一个可以直接运行的 C++ 程序，用于生成符合题目要求的 10 个测试点数据。数据覆盖了小范围、特殊性质（$7k, 7k+1$）以及最大范围。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <random>
#include <ctime>

using namespace std;

// 随机数生成器
mt19937 rng(time(0));

int rand_int(int min, int max) {
    if (min > max) return min;
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

// 解决函数，用于生成 .out 文件 (复用上面的 Solution)
const int costs[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

string solve_algo(int n) {
    if (n == 1) return "-1";
    if (n <= 14) {
        int ans[] = {0, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88};
        return to_string(ans[n]);
    }
    
    string res = "";
    int digits = (n + 6) / 7;
    
    for (int i = 1; i <= digits; ++i) {
        int start_d = (i == 1) ? 1 : 0;
        for (int d = start_d; d <= 9; ++d) {
            int cost = costs[d];
            int rem_sticks = n - cost;
            int rem_digits = digits - i;
            
            if (rem_sticks >= rem_digits * 2 && rem_sticks <= rem_digits * 7) {
                res += to_string(d);
                n -= cost;
                if (rem_digits > 0 && rem_sticks == rem_digits * 7) {
                    for (int k = 0; k < rem_digits; ++k) res += '8';
                    return res;
                }
                break;
            }
        }
    }
    return res;
}

void generate(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    int T = 50; // 题目数据范围 T <= 50
    fin << T << endl;

    for (int i = 0; i < T; ++i) {
        int n;
        // 根据测试点编号生成不同特征的数据
        if (id == 1) { // n <= 20, 包含很多小数据
            n = rand_int(1, 20);
        } else if (id == 2) { // n <= 50
            n = rand_int(20, 50);
        } else if (id == 3) { // n <= 1000, 特殊性质 A (7的倍数)
            int k = rand_int(15, 140); // 100 <= n <= 1000
            n = k * 7;
        } else if (id == 4) { // n <= 10^5, 特殊性质 A
            int k = rand_int(14200, 14280); 
            n = k * 7;
        } else if (id == 5) { // n <= 10^5, 特殊性质 A (更大范围随机)
             int k = rand_int(100, 14000);
             n = k * 7;
        } else if (id == 6) { // n <= 1000, 特殊性质 B (7k+1)
            int k = rand_int(15, 140);
            n = k * 7 + 1;
        } else if (id == 7) { // n <= 10^5, 特殊性质 B
            int k = rand_int(14200, 14280);
            n = k * 7 + 1;
        } else if (id == 8) { // n <= 10^5, 特殊性质 B
            int k = rand_int(100, 14000);
            n = k * 7 + 1;
        } else if (id == 9) { // n <= 1000, 无特殊性质
            n = rand_int(100, 1000);
        } else { // id == 10, n <= 10^5, 混合
            // 混合一些边界和随机
            if (i < 10) n = rand_int(99900, 100000);
            else if (i < 20) n = rand_int(100, 200);
            else n = rand_int(1, 100000);
        }

        fin << n << endl;
        fout << solve_algo(n) << endl;
    }

    fin.close();
    fout.close();
    cout << "Generated Test Point " << id << endl;
}

int main() {
    for (int i = 1; i <= 10; ++i) {
        generate(i);
    }
    cout << "Done." << endl;
    return 0;
}