「CSP-J 2024真题解密」洛谷P11229小木棍：数字拼合问题的递归解法精讲 附完整代码实现

一、题目解读

本题要求用特定数量的小木棍拼出合法数字：

• 核心规则：每个数字对应固定数量的小木棍（如1用2根，7用3根）

• 输入输出：给定t组测试数据，每组指定可用木棍数，输出能组成的最大数字

• 特殊约束：

• 首位不能为0（需特殊处理）

• 必须用完所有木棍

• 算法特点：需要兼顾数字大小和木棍消耗的最优组合

二、解题思路分析

1. 预处理设计：

• retnum数组存储基础数字的木棍消耗

• retstick数组记录数字0-9对应的木棍数

2. 递归策略：

• 分治思想：将大问题分解为子问题

• 贪心选择：优先尝试较大数字

3. 关键优化：

• 首位特殊标记（first变量）

• 数学估算最小所需数字位数（(s+6)/7）

三、解题步骤分解

1. 初始化阶段：

• 读取测试用例数量t

• 重置首位标记first = 1

2. 递归构建数字：

   // 核心递归逻辑：
   if (剩余木棍≤7) 返回基础解
   else:
       计算理论最小位数n
       从9到0尝试每个数字：
           若能减少所需位数：
               选择该数字并递归处理剩余木棍

3. 结果修正：

• 处理首位为0的特殊情况

四、完整代码实现（带注释）

#include<iostream>
#include<string>
using namespace std;

// 数字对应木棍数：0-7分别需要6,2,5,5,4,5,6,3,7,6根
int retstick[10] = { 6,2,5,5,4,5,6,3,7,6 };

// 基础情况返回值（木棍数≤7时）
int retnum[8] = { -1,-1,1,7,4,2,0,8 };

int first = 1; // 首位标记

string stick(int s) {
    if (s <= 7) { // 基础情况处理
        first = 0;
        return to_string(retnum[s]);
    } else {
        int n = (s + 6) / 7; // 计算最小位数
        string tmp = "";
        for (int i = first ? 9 : 0; i >= 0; i--) {
            if ((s - retstick[i] + 6) / 7 < n) {
                tmp = to_string(i);
                first = 0;
                tmp += stick(s - retstick[i]);
                break;
            }
        }
        return tmp;
    }
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        first = 1; // 重置首位标记
        int sticks;
        cin >> sticks;
        string out = stick(sticks);
        if (out[0] == '0') out[0] = '6'; // 首位修正
        cout << out << endl;
    }
    return 0;
}

五、算法总结

1. 时间复杂度：O(t*n) 其中n为数字位数

2. 空间复杂度：O(n) 递归栈深度

3. 算法亮点：

• 预处理加速查询

• 数学估算优化搜索

• 首位标记避免前导零

4. 改进方向：

• 记忆化存储中间结果

• 迭代式改写减少栈消耗