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

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，特判那里有点问题。