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

· · 题解

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

题目传送门。

提供一种不一样的做法，仅供参考。

思路：贪心+最短路/筛法。

思路

看到这个题，我的第一反应是设 string 类型的 f_i，表示用 i 根能拼成最小的数字。

用 string 类型是因为数字有可能会很大。

这样设出来就可以用一种类似最短路的做法求出这个 f_i，读者也可以理解成一种奇怪的筛法。

代码大概长这样子：

void bfs(int n) // 这里的 bfs 其实就是 spfa
{
    for(int i=0;i<=n;i++)f[i]="-1";
    for(int i=1;i<10;i++)f[d[i]]=Min(f[d[i]],str[i]); // 由于字符串自带的“优秀”的比较大小方式，所以我们还要自己定义一个函数
    for(int i=2;i<=7;i++)q.push(i),b[i]=true;
    while(!q.empty())
    {
        int u=q.front();q.pop(),b[u]=false;
        for(int i=0;i<10;i++)
        {
            string newstr=f[u]+str[i]; // str[i] 是把 i 转换成字符串的 i
            if(u+d[i]>n)continue; // d[i] 是拼成 i 要用的木棍个数
            if(f[u+d[i]]=="-1"||Min(f[u+d[i]],newstr)!=f[u+d[i]])
            {
                f[u+d[i]]=newstr;
                if(!b[u+d[i]])b[u+d[i]]=true,q.push(u+d[i]);
            }
        }
    }
}

其中辅助函数和数组为：

string Min(string &s,string &a)
{
    if(s=="-1")return a;
    else if(a=="-1")return s;
    else if(s.size()<a.size())return s;
    else if(a.size()<s.size())return a;
    else return min(a,s);
}
string str[]={"0","1","2","3","4","5","6","7","8","9"};
int d[]={6,2,5,5,4,5,6,3,7,6};

先预处理，后面直接 O(1) 输出答案： f_n。

然后就好了。

优化

好了个蛋啊。。。

首先，考场我写出这个代码来，发现最大样例要 1.2 秒，有点担心 ccf 老爷机过不了。

其次，赛后我在洛谷提交这个代码，发现全 MLE 了，大概原因是 queue 长度太长了。

考虑贪心优化。

发现同等情况下，在后面拼一个 8 是最划算，因为它消耗的木棍数最多，所以最后拼出来的长度一定最小。

然后经过一番输出答案发现，开头的几位数与 8 无关，即可以拼其他的数字。

（考场用代码测试了一下，大概是五六位左右。）

于是我们只需要预处理出来前几位的 f 值，后面全拼 8 就好了。

需要枚举分多少个木棍给前面用，然后后面全拼 8，答案取最优即可。

const int texttime=1e4; // 这个能开 50，考场为了保险开了 1e4
bfs(texttime);

处理部分只需要这样就好了：

int n=in(),id=0,min8=0;
if(n<=texttime){outs(f[n]),putchar('\n');continue;} // 本身就小于的不用处理了
for(int i=0;i<=texttime;i++) // 枚举分给前面多少木棍
    if(f[i]!="-1"&&(n-i)%7==0) // 后面拼 8 拼得尽才行
    {
        int siz=f[id].size();
        if(f[id]=="-1")siz=1e9;
        if(siz+min8>f[i].size()+(n-i)/7)id=i,min8=(n-i)/7;
        else if(siz+min8==f[i].size()+(n-i)/7&&check(f[id],f[i]))id=i,min8=(n-i)/7; // 记录最优
    }
outs(f[id]);while(min8--)putchar('8');putchar('\n'); // 输出结果

其中的 check 函数是比较拼完 8 后的大小用的：

bool check(string a,string b)
{
    while(a.size()<b.size())a+="8";
    while(b.size()<a.size())b+="8";
    return a>b;
}

这样就做完了，这次是真的做完了。

我考场对拍了数据范围以内的所有数字，这种操作方法与最短路的结果无异。

AC 代码（考场代码）

我比较菜，想不出来规律，打不出来表。

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10;
string f[N];
int d[]={6,2,5,5,4,5,6,3,7,6};
queue<int>q;bool b[N];
string Min(string &s,string &a)
{
    if(s=="-1")return a;
    else if(a=="-1")return s;
    else if(s.size()<a.size())return s;
    else if(a.size()<s.size())return a;
    else return min(a,s);
}
string str[]={"0","1","2","3","4","5","6","7","8","9"};
void bfs(int n)
{
    for(int i=0;i<=n;i++)f[i]="-1";
    for(int i=1;i<10;i++)f[d[i]]=Min(f[d[i]],str[i]);
    for(int i=2;i<=7;i++)q.push(i),b[i]=true;
    while(!q.empty())
    {
        int u=q.front();q.pop(),b[u]=false;
        for(int i=0;i<10;i++)
        {
            string newstr=f[u]+str[i];
            if(u+d[i]>n)continue;
            if(f[u+d[i]]=="-1"||Min(f[u+d[i]],newstr)!=f[u+d[i]])
            {
                f[u+d[i]]=newstr;
                if(!b[u+d[i]])b[u+d[i]]=true,q.push(u+d[i]);
            }
        }
    }
    /*int ans=0;
    for(int i=0;i<=1e5;i++)
    {
        for(int j=f[i].size()-1;j>=0;j--)
            if(f[i][j]!='8'){ans=max(ans,j+1);break;}
    }
    out(ans);*/ // 这一段就是我用来测试前面最多有多少位非 8 的
}
void outs(string &s){for(int i=0;i<s.size();i++)putchar(s[i]);}
bool check(string a,string b)
{
    while(a.size()<b.size())a+="8";
    while(b.size()<a.size())b+="8";
    return a>b;
}
int main()
{
    //freopen("sticks.in","r",stdin),freopen("sticks.out","w",stdout);
    const int texttime=1e4;
    bfs(texttime);int t=in();
    while(t--)
    {
        int n=in(),id=0,min8=0;
        if(n<=texttime){outs(f[n]),putchar('\n');continue;}
        for(int i=0;i<=texttime;i++)
            if(f[i]!="-1"&&(n-i)%7==0)
            {
                int siz=f[id].size();
                if(f[id]=="-1")siz=1e9;
                if(siz+min8>f[i].size()+(n-i)/7)id=i,min8=(n-i)/7;
                else if(siz+min8==f[i].size()+(n-i)/7&&check(f[id],f[i]))id=i,min8=(n-i)/7;
            }
        outs(f[id]);while(min8--)putchar('8');putchar('\n');
        //string s=f[id];while(min8--)s+="8";
        //if(s!=f[n])cout<<i<<" : "<<s<<"   "<<f[id]<<"\n",exit(0);
        //else cout<<i<<" ok\n"; // 对拍用
    }
    return 0;
}

后记：推荐一下游记。