CSP-J2024T3题解

· · 个人记录

CSP-J 2024 T3题解

前言

貌似都没有写递归的，特此发一篇题解。

正文

找规律是一个办法，在此提供一种更直接的 暴力 办法。

找到最小位数

首先，我们知道要拼出一个最小的数肯定要先让位数最小，举个简单的例子：

在火柴棒根数都等于7时,

10 \gt 8

所以，第一步显然就是确定最小的位数。

可以做一个有关拼出火柴棒根数字的表格：

int use[]={6,2,5,5,4,5,6,3,7,6};

制作完表格后发现能多填数字 8 时，位数最小。

注意是 位数最小 ，不一定是 数字最小 ，因为我们可以将一个 8 拆解成更小的数字，经过一系列调整而不去改变数字，使得数字更小。

但是，虽然都填 8 时位数最小（数字不一定会最小），能都填 8 吗？

显然不能，会残留一些数字。

所以我们把手里有的火柴棒根数对 7 取模数，有如下 7 种情况（以下设火柴棒根数是 n , 假设 n \gt 7）。

发现了什么？

给定火柴棒之后，最小数字的位数可以确定。

那位数是多少？

根据观察上述的 7 种情况，发现位数最小是 \lceil \frac{n}{7} \rceil （n 除以 7 上取整）。

确定了最小位数，我们就可以写一个暴搜！

哪些数字可以被拼出来

这个地方需要一点点 DP 的思想（没事，看不懂通过观察样例和盲猜也可以知道只有1根火柴棒拼不出来）。

这道题 货币系统。

发现可以将每个数字所用的火柴棒数量作为货币价值，从 1 枚举到 10^5 （火柴棒的最大根数），做一个货币系统就行了。

发现只有 1 根火柴棒的时候拼不出来任何数字。

暴搜

到了大家最喜欢的暴力环节 。

有了最小位数，我们就可以对于每一位进行搜索。

时间复杂度 O(n^9) ,实际得分 20 Pts 。

戳这里

代码 

#include <bits/stdc++.h>

using namespace std;

const int N=1e5;

int t,n;
int use[]={6,2,5,5,4,5,6,3,7,6};
int now[N];
int min_num;
int minn[N];

void init() {
    memset(minn,0x3f,sizeof minn);
    memset(now,0,sizeof now);
}

void readin() {
    cin>>n;
}

void get_num() {
    min_num=(n+6)/7;
}

void dfs(int stp,int res) {
    if(stp==min_num+1) {
        if(res!=0) return;
        for(int i=1;i<=min_num;++i){
            if(now[i]>minn[i]) return;
        }
        for(int i=1;i<=min_num;++i){
            minn[i]=now[i];
        }
        return;
    }
    for(int i=0;i<=9;++i){
        if(i==0&&stp==1) continue;
        if(use[i]>res) continue;
        now[stp]=i;
        dfs(stp+1,res-use[i]);
    }
}

void output() {
    for(int i=1;i<=min_num;++i){
        cout<<minn[i];
    }
    cout<<"\n";
}

void solve() {
    readin();
    if(n==1) cout<<-1<<"\n";
    else{
        init();
        get_num();
        dfs(1,n);
        output();
    }
}

signed main() {
    cin>>t;
    while(t--) {
        solve();
    }   
    return 0;
}

正解

可以发现，我们每一次进行枚举搜出来的解都是最优解，直接结束即可。

但是只能得到 20 Pts （提交记录先不放了）。

所以，超级 剪枝解决问题。

当如下两种情况发生时，可以退出。

1.剩余步骤都填数字 8 都填不满。

2.剩余步骤都填最小的 1 都多了。

可以得到 100 Pts 代码。

步骤

1.先打出来所有所需要的表 
2.求出最小的位数=(n+6)/7
3.标记minn[]（记录当前最小的数的每一位）
4.标记now[] （记录当前数的每一位）
5.输出答案

代码

戳这里

#include <bits/stdc++.h>

using namespace std;

const int N=1e5;

int t,n;
int use[]={6,2,5,5,4,5,6,3,7,6};
int now[N];
int minn[N];
int min_num;
bool flag;

void init() {
    memset(minn,0x3f,sizeof minn);
    memset(now,0,sizeof now);
    flag=0;
}

void readin() {
    cin>>n;
}

void get_num() {
    min_num=(n+6)/7;
}

void dfs(int stp,int res) {
    if(stp==min_num+1) {
        if(res!=0) return;
        for(int i=1;i<=min_num;++i){
            if(now[i]>minn[i]) return;
        }
        for(int i=1;i<=min_num;++i){
            minn[i]=now[i];
            cout<<minn[i];
        }
        cout<<"\n";
        flag=1;
        return;
    }
    if(flag) return;
    if((min_num-stp+1)*7<res) {
        return;
    }
    if((min_num-stp+1)*2>res) return;
    for(int i=0;i<=9;++i){
        if(i==0&&stp==1) continue;
        if(use[i]>minn[i]) continue;
        if(use[i]>res) continue;
        now[stp]=i;
        dfs(stp+1,res-use[i]);
    }
}

void solve() {
    readin();
    if(n==1) cout<<-1<<"\n";
    else{
        init();
        get_num();
        dfs(1,n);
    }
}

signed main() {
    cin>>t;
    while(t--) {
        solve();
    }   
    return 0;
}