[CSP-J 2024] 小木棍 题解

· · 题解

题意简述

你需要用恰好 n 根小木棍拼成一个不含前导零的正整数，求这个数最小是多少。多组数据。

解题思路

这道题的题目描述可以说是前三题中最简单的了。看到很多题解都是打表找规律和动态规划，这里提供一个不一样的偏数论做法。

首先可以根据题目得出一个很简单的结论：要想使这个数最小，它的位数越小越好。不难发现，数字 8 需要用 7 根木棍，是最多的，因此我们先假设全部用数字 8 填充，所以最小位数就是 \lceil \frac{n}{7}\rceil 位。

但是全部用 8 填充可能会又多出来的部分。怎么办呢？我们知道，两个数在位数相同的情况下，先看高位，再看低位。因此我们先计算出多了多少根木棍，然后从高位开始，把 8 变成尽可能小的数。

注意特判一下 n=1 的情况，因为 1 根小木棍不能拼成数字。

主要思路就这些，其余的就不用多讲了，具体注释看代码。

参考代码

#include<bits/stdc++.h>
using namespace std;
int stick[10]={6,2,5,5,4,5,6,3,7,6}; //先计算出每个数字需要的小木棍数量
int T,n;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n==1){
            printf("-1\n");
            continue;
        } //特判
        int tmp=n,rem=(n+6)/7*7-n;
    // tmp 表示还没有用的小木棍数量，rem 表示全为 8 的情况需要减去多少根木棍
        while(tmp>0){
            for(int i=0;i<10;i++){
                if(tmp==n&&i==0) continue; //不能有前导零
                if(tmp<stick[i]) continue; //无法拼成这个数字
                if(7-stick[i]<=rem&&tmp-stick[i]!=1){
                    tmp-=stick[i];
                    rem-=7-stick[i];
                    printf("%d",i);
                    break;
                } //如果可以就选择，这一定是最小的
            }
        }
        printf("\n");
    }
    return 0;
}