题解：P11229 [CSP-J 2024] 小木棍

· · 题解

前言

已经退役成了 whker，到了高二依然没有 AK 过 CSP-J。
显然，今年的题目我做不到 AK，甚至很难上 300 分。
补题，发现了一种完全不同的做法。
相较于各种找规律，更有道理；相较于各种 dp，更加易懂。

思路

思考一下，人类在比较两个数大小的时候是怎么做的？
先考虑数字位数，位数多的数一定大；数位相同，再依次比较前几位。

回到这一题，首先我们要考虑的，是用 n 根小木棍摆出的数字至少要有几位？
显然，因为数字 8 消耗的小木棍最多，所以小木棍全部用来摆数字 8，摆出的数字一定数位最少。

所以我们先将除了第一位的数位填上 8，第一位随便补一个数来满足使用了 n 根小木棍，这样摆出的数字一定数位最少。

再考虑如何让前几位更小。
假设我们先想让第一位数字变得更小，那么唯一的方法就是，从后面的某一位拆一根或几根小木棍下来，装到第一位数字上面。
之前我们的构造方法决定了除了第一位，其他数位上都是数字 8。不难发现，在数字 8 上面拆下一根或几根小木棍下来，一定有方法把 8 变成一个比 8 更小的数。
所以，我们这样一波操作，不仅第一位的数字变小了，拆小木棍的那一位数字也变小了。那么根据贪心，我们应该从第二位拆小木棍，因为这样可以让整体数字更小。
我们肯定想把第一位的数字在添加小木棒后变得最小，那么改变的方案如下（逗号前是如果这一位需要考虑前导零，最小可以变成多少；逗号后则是不需要考虑前导零，最小可以变成多少）：		 初始数字 操作后数字 增加的木棍数
0 0 0
1 1,0 0,4
2 2,0 0,1
3 2,0 0,1
4 2,0 1,2
5 2,0 0,1
6 6,0 0
7 2,0 2,3
8 8 0
9 6,0 0,0

我们最多需要对多少个数位进行改变小木棍数量的操作呢？可以发现，第一位需要小木棍最多的情况，是从第二位拿走两根木棒来 7\to 2，那此时第二位最多也就从第三位拿走一根木棒来 8\to 2\to 0，第三位就直接 8\to 0 了。
经过上述分析，我们发现了一个极其重要的性质：我们之前构造出的数字，和最优答案，只有前三位可能会不一样。

所以把除了前三位都填 8，然后再暴力枚举前三位即可。
这样的复杂度是 O\left(T(n+10^3)\right) 的，还可以把前三位所有情况预处理，后面查询的时候直接查表，时间复杂度为 O(10^3+Tn)。

代码

#include<bits/stdc++.h>
using namespace std;

int nd[1005]={6,2,5,5,4,5,6,3,7,6};
int minn[105];
void work(){
    int n; cin>>n;
    if(n==1){
        cout<<"-1\n";
        return;
    }
    string ans;
    while(n>21){
        n-=7;
        ans.push_back('8');
    }
    cout<<minn[n]<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=999;i++){//打表
        nd[i]=nd[i%10];
        if(i>9)nd[i]+=nd[i/10];
        if(!minn[nd[i]])minn[nd[i]]=i;
    }
    int T; cin>>T;
    while(T--)work();
    return 0;
}