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

· · 题解

考场思路

打表

因为我太弱了，看到这道题一个输入对应一个固定的输出，便想到了深搜打表，因为暴力思路很简单，这里直接公布代码。

优化：因为用木棍摆出的数字中有些使用的木棍数量是一样的，便可以只枚举小的数。

当然，dalao 们也可自己加记忆化搜索。

洛谷10分代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n;
string ans;
string mi(string x,string y){
    int len=x.size();
    for(int i=0;i<len;i++){
        if(x[i]<y[i]) return x;
        if(x[i]>y[i]) return y;
    }
    return x;
}
void dfs(int s,string x){
    if(s>n) return ;
    if(s==n){
        if(ans.size()>x.size()) ans=x;//判断位数 
        else ans=mi(ans,x);//一位一位比较 
        return ;
    }
    dfs(s+6,x+'0');
    dfs(s+2,x+'1');
    dfs(s+5,x+'2');
    dfs(s+4,x+'4');
    dfs(s+3,x+'7');
    dfs(s+7,x+'8');//枚举最小数 
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        ans='1';
        for(int i=1;i<100000;i++) ans+='1';//设为最大值 
        dfs(2,"1");
        dfs(5,"2");
        dfs(4,"4");
        dfs(6,"6");
        dfs(3,"7");
        dfs(7,"8");
        if(ans.size()==100000) cout<<"-1\n";
        else cout<<ans<<"\n";
    }
    return 0;
}

当然，以这种代码打表 10^5 的数据的话，不知道要等到猴年马月，所以只能寻求更高级的算法。

正解（找规律）

经过打表后发现，1 \sim 35 的表如下：

-1
1
7
4
2
6
8
//1
10
18
22
20
28
68
88
//2
108
188
200
208
288
688
888
//3
1088
1888
2008
2088
2888
6888
8888
//4
10888
18888
20088
20888
28888
68888
88888
//5

可以发现它们每 7 个数字，字符数就加 1。

这些数字明显是有规律的（仅限 n\ge 15 时）：

第一个数为 10888\dots。

第二个数为 18888\dots。

第三个数为 20088\dots。

第四个数为 20888\dots。

第五个数为 28888\dots。

第六个数为 68888\dots。

第七个数为 88888\dots。

于是便有了以下代码：

洛谷100分代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n;
int h[105]={0,-1,1,7,4,2,6,8,10,18,22,20,28,68,88};//前14个数字打表
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        if(n<=14) cout<<h[n];
        else{
            int m=(n-1)/7+1;//求出拼出的数字有几位
            n%=7;//n是第几个数
            if(n==1){
                cout<<"10";
                for(int i=3;i<=m;i++) cout<<"8";
            }
            else if(n==2){
                cout<<"1";
                for(int i=2;i<=m;i++) cout<<"8";
            }
            else if(n==3){
                cout<<"200";
                for(int i=4;i<=m;i++) cout<<"8";
            }
            else if(n==4){
                cout<<"20";
                for(int i=3;i<=m;i++) cout<<"8";
            }
            else if(n==5){
                cout<<"2";
                for(int i=2;i<=m;i++) cout<<"8";
            }
            else if(n==6){
                cout<<"6";
                for(int i=2;i<=m;i++) cout<<"8";
            }
            else{
                for(int i=1;i<=m;i++) cout<<"8";
            }
        }
        cout<<"\n";
    }
    return 0;
}