题解：P11229 [CSP-J 2024] 小木棍（民间数据）

Walter_Fang · 2024-10-26 22:19:40 · 题解

题意

用 n 根小木棍摆数，所摆的数不含前导零，求可摆的数的最小值。

解析

首先根据题意可以直接打出一个爆搜，代码如下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2e9,f[10]={6,2,5,5,4,5,6,3,7,6};
ll i,ans;
void dfs(ll gz,ll x){
    if(gz>i)return;
    if(gz==i)return ans=min(ans,x),void();
    for(ll i=0;i<=9;i++){
        if(i==0&&gz==0)continue;
        dfs(gz+f[i],x*10+i);
    }
}
int main(){
    for(i=1;i<=40;i++){
        ans=inf;
        dfs(0,0);
        cout<<i<<"的答案是"<<ans<<'\n';
    }
}

然后我们可以得出 1\leq n\leq40 时的答案如下。（搜到 40 就炸了，实测如果把变量 x 换成 string 类型能搜到 50 左右）。

再瞥一眼特殊性质，不难发现答案跟 7 有点关系，所以将打出的表按对 7 取模的元素整理一下，如下表。

相信做过这一步的人这题都过了。

代码

#include<bits/stdc++.h>
using namespace std;
const int f[10]={0,-1,1,7,4,2,6,8,10};
int T,n,d,i;
int main(){
    for(cin>>T;T--;){
        cin>>n;
        if(n<=8)cout<<f[n];
        else{
            d=n%7;
            if(!d)for(i=1;i<=n/7;i++)cout<<8;
            if(d==1){
                cout<<10;
                for(i=1;i<n/7;i++)cout<<8;
            }
            if(d==2){
                cout<<1;
                for(i=1;i<=n/7;i++)cout<<8;
            }
            if(d==3){
                if(n==10)cout<<22;
                else{
                    cout<<200;
                    for(i=1;i<=n/7-2;i++)cout<<8;
                }
            }
            if(d==4){
                cout<<20;
                for(i=1;i<n/7;i++)cout<<8;
            }
            if(d==5){
                cout<<2;
                for(i=1;i<=n/7;i++)cout<<8;
            }
            if(d==6){
                cout<<6;
                for(i=1;i<=n/7;i++)cout<<8;
            }
        }
        cout<<'\n';
    }
}