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

· · 题解

首先观察数据范围， 1≤n≤10^5 ，看来是不能按位枚举了，肯定TLE。再细看一下测试点数据，n在50之内是没有特殊性质的，说明暴力应该能过，那这个该如何解决？

突然想到比赛前刚好两天的那个晚上、挑灯夜战复习的Dijkstra，由一个点开始计算另外的点的最小距离，这道题能这么干吗？令源点为1 ~ 9（不能有前导0），由此往外扩展，每个结点都有0 ~ 9十种边，再用上堆优化，似乎行得通？

下面是变异版的Dijkstra堆优化：

0.cmp定义（字符串类型的数字的比较规则）

bool cmp(string a,string b)
{
    return a.size()>b.size()||a.size()==b.size()&&a>b;
}
  1. 定义node结构体
struct node
{
    string num;
    ll sum;    //即long long
    bool operator<(const node& T)const{return cmp(num,T.num);}
};
  1. 边权定义（每种数字所需小木棍数量），ans数组（用x根小木棍最少能摆出ans[x]这个数，即最短路）
ll s[10]={6,2,5,5,4,5,6,3,7,6},n,t;
string ans[105];
priority_queue<node>q;
  1. Dijkstra算法
void solveBF()
{
    string inf="",e="",kk;  //e为空串，kk为临时变量（都没用）
    for(ll i=1;i<=30;++i)inf+='1';
    fill(ans+1,ans+1+50,inf);
    for(ll i=1;i<10;++i)
    {
        q.push((node){e+char(i+'0'),s[i]});
        kk=e+char(i+'0');
        if(cmp(ans[s[i]],kk))ans[s[i]]=kk;
    }
    for(node u;!q.empty();)
    {
        u=q.top();q.pop();
        if(cmp(u.num,ans[u.sum]))continue;
        for(ll i=0;i<10;++i)
        {
            string k=u.num+char(i+'0');ll sk=u.sum+s[i];
            if(cmp(ans[sk],k))ans[sk]=k,q.push((node){k,sk});
        }
    }
}

50以内解决了，然后呢？

用solveBF()试了下100以上的数，发现结尾全都是8！

（终于知道特殊性质里的7是哪来的了，8需要7根小木棍）

下面是特殊性质解析：

  1. 特殊性质 A：保证 n 是 7 的倍数且 n≥100 .

    全填8就行了，因为这样保证填出的数的位数最小

    证明：若有一位不填8，则必定会有多余的木棍，这会导致需要多加一位来用完多余木棍

string k="";
for(ll j=1;j<=n/7;++j)k+='8';
puts(k.c_str());
  1. 特殊性质 B：保证存在整数 k 使得 n=7k+1 ，且 n≥100 .

    用solveBF()多试几个（e.g.：50,99），发现都是10加上一连串8

    这也很好理解，因为10需要8根木棍，模7余1，且是木棍数模7余1之中最小的那个

    这就简单了，扔掉8根木棍用来填10，剩下的全填8

string k="10";
for(ll j=1;j<=n/7-1;++j)k+='8';
puts(k.c_str());

好啦，就差一个没有特殊性质的数据了，也就是最大的那组数据

其实把上面两个特殊性质搞定就有思路了，先适当扔掉几根木棍用solveBF()处理，剩下的全填8

准确地说，扔掉的木棍数量和原有木棍数量是模7同余的

那就随便扔掉个四十几根，既保证前面部分是最小的，有保证在solveBF处理范围之内（其实solveBF能到50000保证不会TLE和MLE，其中inf定为8000个1，ans数组用到50000）

ll r=n%7+42;
string k=ans[r];
for(ll j=1;j<=(n-r)/7;++j)k+='8';
puts(k.c_str());

上完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp(string a,string b){return a.size()>b.size()||a.size()==b.size()&&a>b;}
struct node
{
    string num;
    ll sum;
    bool operator<(const node& T)const{return cmp(num,T.num);}
};
ll s[10]={6,2,5,5,4,5,6,3,7,6},n,t;
string ans[105];
priority_queue<node>q;
void solveBF()
{
    string inf="",e="",kk;
    for(ll i=1;i<=30;++i)inf+='1';
    fill(ans+1,ans+1+50,inf);
    for(ll i=1;i<10;++i)
    {
        q.push((node){e+char(i+'0'),s[i]});
        kk=e+char(i+'0');
        if(cmp(ans[s[i]],kk))ans[s[i]]=kk;
    }
    for(node u;!q.empty();)
    {
        u=q.top();q.pop();
        if(cmp(u.num,ans[u.sum]))continue;
        for(ll i=0;i<10;++i)
        {
            string k=u.num+char(i+'0');ll sk=u.sum+s[i];
            if(cmp(ans[sk],k))ans[sk]=k,q.push((node){k,sk});
        }
    }
}
int main()
{
//  freopen("sticks.in","r",stdin);
//  freopen("sticks.out","w",stdout);
    scanf("%lld",&t);
    solveBF();
    for(ll i=1;i<=t;++i)
    {
        scanf("%lld",&n);
        if(n<=1)puts("-1");
        else
        {
            if(n<=50)puts(ans[n].c_str());
            else if(n%7==0)
            {
                string k="";
                for(ll j=1;j<=n/7;++j)k+='8';
                puts(k.c_str());
            }
            else if(n%7==1)
            {
                string k="10";
                for(ll j=1;j<=n/7-1;++j)k+='8';
                puts(k.c_str());
            }
            else
            {
                ll r=n%7+42;
                string k=ans[r];
                for(ll j=1;j<=(n-r)/7;++j)k+='8';
                puts(k.c_str());
            }
        }
    }
    return 0;
}

Notice：分享一下，本蒟蒻考试的那份代码，处理特殊性质那边的代码里，for循环用的是i，竟然没错，涨知识了……

e.g.:以下代码的运行结果为90

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
int main()
{
    for(ll i=1;i<=10;++i)for(ll i=1;i<=9;++i)++ans;
    printf("%lld\n",ans);
    return 0;
}

感谢观看！~