P11229 [CSP-J 2024] 小木棍

· · 题解

先看一下题目，显然可以发现这道题目是具有动态规划的性质的，是个模板，所以先写下来。

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

struct node{
    string d;
    int w;
};
int q,n,mi,flag;
string mis,t;
node dp[1010];
bool dx(string a,string b){
    int len=a.length();
    for (int i=0;i<len;i++){
        if (a[i]-'0'<b[i]-'0')  return 1;
        if (a[i]-'0'>b[i]-'0')  return 0;
    }
    return 0;
}
int main(){
    cin>>q;
    dp[0].d=dp[1].d="a",dp[2].d="1",dp[3].d="7",dp[4].d="4",dp[5].d="2",dp[6].d="0",dp[7].d="8";
    dp[0].w=dp[1].w=dp[2].w=dp[3].w=dp[4].w=dp[5].w=dp[6].w=dp[7].w=1;
    for (int i=8;i<=1000;i++){
        mi=INT_MAX,flag=0;
        for (int j=2;j<=i-2;j++)  mi=min(dp[j].w+dp[i-j].w,mi);
        dp[i].w=mi;
        for (int j=2;j<=i-2;j++){
            if (dp[j].w+dp[i-j].w==mi){
                t=dp[j].d+dp[i-j].d;
                for (int k=0;k<=t.size();k++){
                    if (t[k]=='0')  t[k]='6';
                    else  break;
                }
                if (!flag){
                    mis=t;
                    flag=1;
                }else{
                    if (dx(t,mis)){
                        mis=t;
                    }
                }
            }
        }
        dp[i].d=mis;
    }
    while (q--){
        cin>>n;
        if (n%7==0){
            for (int i=0;i<n/7;i++)  cout<<8;
            cout<<"\n";
        }else if (dp[n].d=="a")  cout<<"-1\n";
        else if (n==6)  cout<<"6\n";
        else  cout<<dp[n].d<<"\n";
    }
    return 0;
}

直接跑只有70pts，我们可以打一个表看看。

int dp[]={-1,1,7,4,2,6,8,10,18,22,20,28,68,88,108,188,200,208,288,688,888,1088,1888,2008,2088,2888,6888,8888,10888,18888,20088,20888,28888,68888,88888,108888,188888,200888,208888,288888,688888,888888,1088888,1888888,2008888,2088888,2888888,6888888,8888888,10888888,18888888,20088888,20888888,28888888,68888888,88888888,108888888,188888888,200888888,208888888,288888888,688888888,888888888,1088888888,1888888888,2008888888,2088888888,2888888888,6888888888,8888888888,10888888888,18888888888,20088888888};

很多连续的8，如果花点时间打完的话，你会发现代码太长了，评测机不吃，所以我们要优化一下。写一个转换器。

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

int n;
string s;
int main() {
    freopen("P11229.txt", "r", stdin);
    freopen("P11229.in", "w", stdout);//后期
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>s;
        int cnt=0,flag=0;
        for (int j=0;j<s.size();j++) {
            if (s[j]=='8') {
                flag=1;
                break;
            }
            cnt++;
        }
        if (flag) {
            if (cnt==0)  cout<<-2<<",";//只有8的我们用-2填充
            else{
                for (int k=0;k<cnt;k++) {
                    cout<<s[k];
                }
                cout<<",";
            }
        }else  cout<<s<<",";//直接填充,方便我们黏贴到数组中
    }

    return 0;
}

上面这份代码得到了非8部分，下面这份代码会得到8的数量。

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

int n;
string s;
int main(){
    freopen("P11229.txt","r",stdin);
    freopen("8_P11229.in","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>s;
        int cnt=0,flag=0;
        for (int j=0;j<s.size();j++){
            if (s[j]=='8'){
                flag=1;
                break;
            }
            cnt++;
        }
        if (flag){
            int num8=0;
            for (int j=cnt;j<s.size();j++){
                if (s[j]=='8')  num8++;
                else  break;
            }
            cout<<num8<< ",";
        }else{
            cout<<0<< ",";
        }
    }

    return 0;
}

然后我们写一份AC code。

数组A 数组B

然后，

洛谷你逗我呢！