题解：AT_abc443_f [ABC443F] Non-Increasing Number / [SNOW] - 19

· · 题解

刚过（

考虑大力搜索。具体的，我们不断的从已有状态进行转移，选择一个合法的数字接在原数字末尾。

注意到对于模 n 同余且尾数相同的两个数一定只需要考虑较小的那一个。

于是 vis 数组的定义就出来了。

使用 bfs 保证第一个抵达的是最小的结果，时间复杂度也容易发现是 O(Vn)，其中数字种类 V=10。

做完了……吗？

你准备如何实现呢。

队列里面存放输出的结果和余数吗？恭喜你，字符串拼接的大常数炸飞你。

正确做法是存末尾数字和余数，然后另外开个链表，最后沿着链表把答案拎出来。

MLE 了？请不要使用 #define int long long。

做完了。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define mod 998244353
using namespace std;
int vis[3000005][15];
int pre[3000005][15];
int out[3000005][15];
void solve(){
    int n;
    cin>>n;
    queue<pair<int,int>>q;
    if(n%10==0){
        cout<<-1;
        return;
    }
    if(n<10){
        cout<<n;
        return;
    }
    for(int i=1;i<10;i++){
        q.push({i,i});
        vis[i][i]=1;
        pre[i][i]=-1;
        out[i][i]=-1;
    }
    while(!q.empty()){
        int s=q.front().first;
        int x=q.front().second;
        q.pop();
        if(x==0){
            string ret;
            char c=s+'0';ret+=c;
            for(int i=pre[x][s],j=out[x][s];i!=-1;){
                c=j+'0';
                ret+=c;
                int xi=i;
                int xj=j;
                i=pre[xi][xj];
                j=out[xi][xj];
            }
            reverse(ret.begin(),ret.end());
            cout<<ret;
            return;
        }
        for(int i=s;i<10;i++){
            int nx=x;
            nx=nx*10+i;
            nx%=n;
            if(!vis[nx][i]){
                out[nx][i]=s;
                pre[nx][i]=x;
                q.push({i,nx}),vis[nx][i]=1;
            }
        }
    }
    puts("-1");
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
// 她的目的地是大街旁的路边摊。
// 那里好像是间诚实商店，只有放著投钱的钱箱。

// 她在那里做了坏事。
// 所以我也立刻出面制止。

//「不可以喔，要好好付钱才对。」

// 边说，我边把手放上她的肩膀。

交了 9 发。