HDU 4474 Yet Another Multiple Problem【2012成都regional K题】

不怪任何人，就当什么都没有发生吧，虽然结果悲剧

与之前网络赛那题相似(似乎更简单一点)

BFS，路径u->v且v=10*u+i,第一次搜到即为最优值,

就是一个裸的BFS，不是什么DP、数位DP……那些什么乱乱的东西，更不是暴力枚举倍数

http://acm.hdu.edu.cn/showproblem.php?pid=4474

#include<cstdio>#include<cstring>int a[10],n,m,bg,ed;int q[11111],pre[11111],val[11111];void pnt(int u){    if(pre[u]) pnt(pre[u]);    putchar(val[u]+48);}void solve(){    bg=ed=0;    for(int i=1;i<10;i++) if(i%n==0){printf("%d\n",i);return;}    for(int i=1;i<10;i++) if(!a[i]) q[ed++]=i%n,pre[i%n]=0,val[i%n]=i;    while(bg<ed)    {        int u=q[bg++];        for(int i=0;i<10;i++) if(!a[i])        {            int v=(u*10+i)%n;            if(v==0)            {                pnt(u);                printf("%d\n",i);                return;            }            if(-1==pre[v]) q[ed++]=v,pre[v]=u,val[v]=i;        }    }    puts("-1");}int main(){    freopen("in.txt","r",stdin);    int cas=1;    while(scanf("%d",&n)!=EOF)    {        memset(pre,-1,sizeof(pre));        memset(a,0,sizeof(a));        scanf("%d",&m);        for(int x,i=0;i<m;i++)        {            scanf("%d",&x);            a[x]=1;        }        printf("Case %d: ",cas++);        solve();    }    return 0;}

http://acm.hdu.edu.cn/showproblem.php?pid=4294

http://blog.csdn.net/wxfwxf328/article/details/8037588#t5

1楼hundundm昨天 18:45

哇，这写法比我的好多了Orz，学习学习nn话说似乎有点小bugn5 1n5n这样的话，你的程序会输出5，答案应该是10，特判那里有点问题。