uva1653

本来想刷道签到题结果被卡住了。这题题意描述有点问题，数字又不一定都是个位数。。。难道是我英语太差了？ digits就表示0~9这几个数？唉，还是太弱了。这题就是用了一个bfs，应该说还是有点意思的，直接模拟复杂度肯定爆炸，而且还不好判无解的情况。而bfs复杂度是n*10的，因为%n相同的状态搜索过程都是相同的，相当于一堆循环节，而无解的情况也好判了，状态都搜完后还没有%n为0的就无解了，因为剩下的都是一堆循环节，也不可能搜到解了。

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

struct node{

    int m,f,x;

}q[maxn],A,B;

int cas,n,m,can[],head,tail,vis[maxn],flag;

void print(int x){

    if(!x)return;

    print(q[x].f);

    printf("%d",q[x].x);

}

int main(){

    while(scanf("%d%d",&n,&m)!=EOF){

        ++cas;flag=;int x;

        memset(vis,,sizeof(vis));

        memset(can,,sizeof(can));

        for(int i=;i<=m;++i){

            scanf("%d",&x);can[x]=;

        }

        printf("Case %d: ",cas);

        head=tail=;

        for(int i=;i<=;++i)if(!can[i]){

            A.m=i%n;A.x=i;A.f=;

            if(!A.m){printf("%d\n",i);flag=;break;}

            if(!vis[A.m]){

                q[++tail]=A;vis[A.m]=;

            }

        }

        if(flag)continue;

        while(head<tail){

            B=q[++head];

            for(int i=;i<=;++i)if(!can[i]){

                A.m=(B.m*+i)%n;

                A.x=i;A.f=head;

                if(vis[A.m])continue;

                vis[A.m]=;q[++tail]=A;

                if(!A.m){flag=;break;}

            }

            if(flag)break;

        }

        if(flag){

            print(tail);printf("\n");

        }

        else{puts("-1");}

    }

    //system("pause");

    return ;

}

/*

2345 3

7 8 9

100 1

0

*/

巴特西

uva1653

最新文章

热门文章