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

ZMQ_Ink6556 · 2024-10-28 17:26:09 · 题解

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

小木棍是爆搜剪枝，所以小木棍也是爆搜剪枝。

爆搜剪枝款。

解题思路

显而易见，位数少的数一定比位数多的数小。所以我们可以先求出最小位数 = \lceil \frac{n}{7}\rceil，原理其它题解已经讲述的很清楚了，在此就不再赘述。

暴力也很简单，从小到大枚举最小位数每一位分别放 0 至 9 的方法，遇到的第一个可行方案，复杂度 O(10^n)。

此时，加入一个极其简单的剪枝，如果剩余的 n 不能够被以剩余的位数拼成（即使全放 8 也不够的时候），直接退出搜索即可。

if(ceil(1.0 * 剩余的 $n$ / 7.0) + 已经拼过的位数 - 1 > 最小位数)
{
    return 0;
}

复杂度分析：玄学 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
int t , n , maxws , ans[100005];
const int cost[10] = {6 , 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6};
bool dfs(int deep , int nless)
{
    if(deep > maxws)
    {
        if(nless == 0)
        {
            return 1;
        }
        return 0;
    }
    if(ceil(1.0 * nless / 7.0) + deep - 1 > maxws)
    {
        return 0;
    }
    if(deep == 1)
    {
        for(int i = 1 ; i <= 9 ; i++)
        {
            if(dfs(deep + 1 , nless - cost[i]))
            {
                ans[deep] = i;
                return 1;
            }
        }
        return 0;
    }
    for(int i = 0 ; i <= 9 ; i++)
    {
        if(dfs(deep + 1 , nless - cost[i]))
        {
            ans[deep] = i;
            return 1;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n;
        if(n == 1)
        {
            cout << "-1\n";
            continue;
        }
        maxws = ceil(1.0 * n / 7.0);
        dfs(1 , n);
        for(int i = 1 ; i <= maxws ; i++)
        {
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}