CSUST Number Game 题解(bfs+思维)

题目链接

题目思路

第一眼肯定以为是暴力题，其实答案最长可以答案\(10^6\)位

那么求最小的数，并且是数位问题，肯定是\(bfs\)

然后\(bfs\) ，顺便记录对\(k\)的余数即可，说起来有点麻烦，看代码即可

如对k的余数出现多次，显然只需要第一次出现的数即可

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int k,t,cnt;
int ban[20];
bool vis[maxn];
int lastch[maxn];
int lastid[maxn];
signed main(){
    scanf("%d%d",&k,&t);
    for(int i=1,x;i<=t;i++){
        scanf("%d",&x);
        ban[x]=1;
    }
    queue<pair<int,int>> que;
    cnt++;
    que.push({cnt,0});
    while(!que.empty()){
        int id=que.front().fi;
        int val=que.front().se;
        que.pop();
        for(int i=0;i<=9;i++){
            if(ban[i]) continue;
            int nxt=(val*10+i)%k;
            if(vis[nxt]) continue;
            // 0
            if(nxt==0){
                if(cnt==1&&i==0){
                    continue;
                }else{
                    vector<int> pr;
                    pr.push_back(i);
                    while(id>1){
                        pr.push_back(lastch[id]);
                        id=lastid[id];
                    }
                    reverse(pr.begin(),pr.end());
                    for(auto x:pr){
                        printf("%d",x);
                    }
                }
                return 0;
            }
            // 0
            vis[nxt]=1;
            ++cnt;
            lastch[cnt]=i;
            lastid[cnt]=id;
            que.push({cnt,nxt});
        }
    }
    printf("-1\n");
    return 0;
}