洛谷——P1602 Sramoc问题

P1602 Sramoc问题

$bfs$搜索

保证第一个搜到的符合条件的就是最小的

#include<bits/stdc++.h>

#define N 110000
using namespace std;

int m,k;
struct node{
    int x,i,last;
}q[N];

bool M[N];

void print(int x){
    if(q[x].last==0){printf("%d",q[x].x);return;};
    print(q[x].last);
    printf("%d",q[x].i);
}

int main()
{
    scanf("%d%d",&k,&m);
    int t=0;
    for(int i=1;i<k;i++){
        if(i%m==0){
            printf("%d",i);
            return 0;
        }
        else {
            M[i%m]=1;
            q[++t].x=i%m;
            q[t].i=i;
            q[t].last=0;
        }
    }
    
    int h=1;
    while(h<=t){
        for(int i=0;i<k;i++){
            int x=(q[h].x*10+i)%m;
            if(M[x]==1) continue;
            M[x]=1;
            q[++t].x=x;
            q[t].last=h;
            q[t].i=i;
            if(x%m==0){
                print(t);
                return 0;
            }
        }++h;
    }
    
    return 0;
}