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

ylch · 2024-12-07 20:48:16 · 题解

提供一种新思路。很简单，基于爆搜。

对于找规律的做法，在许多题解中都有说明。我们由特殊性质和暴力打表可知，这道题的关键在 8 这个数字上。

附：n=1 \sim 39 时的爆搜表（来自 @Walter_Fang）

我们可以发现，最终答案一定是由其他数字和若干个 8 组成。那么有一个显然的思路：把结尾固定的 8 的个数算出来，然后剩下的前面几位爆搜确定最优答案。

确定 8 的个数：因为 8 需要用 7 个木棍，所以我们考虑从 21 开始（前面的不好找规律，直接爆搜），将每 7 个作为一组固定的 8 的个数。公式：cnt_n=\lfloor\dfrac{n-14}{7}\rfloor。

爆搜：当 n \le 20 时，直接暴力即可；因为题目要求数字尽可能小，所以当要用的木棍个数相同时（例如 [2,3,5] 和 [6,9]），我们应优先使用数值更小的（2 和 6），这样保证最优。

代码比较简洁易懂：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

int T, num[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
//              0  1  2  3  4  5  6  7  8  9
string ans;
bool cmp(string s, string t){
    if(s.size() == t.size()) return s < t;
    return s.size() < t.size();
}

void dfs(int n, string s){
    if(n == 0){
        if(ans == "" || cmp(s, ans)) ans = s;
        return ;
    }
    for(int i = 0; i < 10; i ++){
        if(s == "" && i == 0) continue;
        if(i == 3 || i == 5 || i == 9) continue;
        if(n >= num[i]) dfs(n - num[i], s + to_string(i));
    }
}

void solve()
{
    ans = ""; // 清空！！！
    int n; cin >> n;
    if(n == 1) cout << -1 << '\n';
    else if(n <= 20){
        dfs(n, "");
        cout << ans << '\n';
    }
    else{
        string tmp = string((n - 14) / 7, '8');
        dfs(n - (n - 14) / 7 * 7, "");
        cout << ans + tmp << '\n';
    }
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}