首页 > 代码库 > [bfs+余数判重+路径记录] hdu 4474 Yet Another Multiple Problem
[bfs+余数判重+路径记录] hdu 4474 Yet Another Multiple Problem
题意:
给一个n和m个数字(一位数)
求最小的n的倍数不含有这m个数字,不存在输出-1
思路:
首先有可能这个数超long long 所以无法暴力解决
所以这题应该是一个bfs
为什么能用余数判重呢
对于当前的余数进到队列里,一定是这个余数对应数的最小值
接下来再怎么添加到满足条件的后续东西应该是一样的
所以就可以余数判重了,类似数位dp的记录方式
然后再加上一个路径记录就好了
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"map" #include"iostream" using namespace std; int used[12]; struct node { int f,pre,now; //f为是否出现,pre前驱,now当前的值 }mark[12345]; int n,m; void dfs(int x) //打印路径 { if(mark[x].pre) dfs(mark[x].pre); printf("%d",mark[x].now); } void bfs() { int cur,next; queue<int>q; for(int i=1;i<=9;i++) //没有前导0 所以先放一位,所以一位数的时候要特判 { if(used[i]) continue; q.push(i); mark[i].f=1; mark[i].pre=0; mark[i].now=i; } while(!q.empty()) { cur=q.front(); q.pop(); for(int i=0;i<10;i++) { if(used[i]) continue; next=(cur*10+i)%n; if(mark[next].f) continue; mark[next].f=1; mark[next].now=i; mark[next].pre=cur; if(next==0) //满足倍数 { dfs(next); return ; } q.push(next); } } printf("%d",-1); } int main() { int cas=1; while(scanf("%d%d",&n,&m)!=-1) { memset(used,0,sizeof(used)); for(int i=0; i<m; i++) { int x; scanf("%d",&x); used[x]=1; } printf("Case %d: ",cas++); if(n<10&&!used[n]) //特判 { printf("%d\n",n); continue; } memset(mark,0,sizeof(mark)); bfs(); puts(""); } return 0; }
[bfs+余数判重+路径记录] hdu 4474 Yet Another Multiple Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。