首页 > 代码库 > hdu 4474 BFS+思维题
hdu 4474 BFS+思维题
http://acm.hdu.edu.cn/showproblem.php?pid=4474
如果A%n ==B %n (A<B) 那么A接下来A经若干次填位数使得A‘%n==0,这个过程也可以使B‘%n==0 但是显然A更小,所以开一个1e4的数组判重
犯得二逼错误:
1、需要记录每一位,不是mod%10就是每一位
2、第一位枚举1~9,但是仍然需要%n
3、必然需要高精度,开始ll WA到死
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define ll long long const int MAXN = 10100; const ll INF = 1e18; int vis[20]; bool r[MAXN]; int n,m; string ans; struct Node{ int mod,pre,id,r; }nodes[MAXN*100];// inline int legal(int t){ while(t) { if(vis[t%10])return 0; t/=10; } return 1; } ll flag,tmp; void print(Node t) { if(t.pre!=-1) { print(nodes[t.pre]); ans+=t.r+'0'; } else ans+=t.r+'0'; } void solve() { queue<Node>q; int id=0; for(int i=1;i<=9;i++){ if(!r[i%n] && !vis[i]) { r[i%n]=1; nodes[id].mod=i%n,nodes[id].pre=-1,nodes[id].id=id,nodes[id].r=i; q.push(nodes[id]); id++; } } while(!q.empty()){ Node tp=q.front(); if(tp.mod%n == 0){print(tp);flag=0;return;}//******* q.pop(); for(int i=0;i<=9;i++) if(!vis[i]){ int t=tp.mod*10+i; t%=n; if(!r[t]){ r[t]=1; nodes[id].mod=t,nodes[id].pre=tp.id,nodes[id].id=id,nodes[id].r=i; q.push(nodes[id]); id++; } } } } int main() { //IN("hdu4474.txt"); int ic=0,u; while(~scanf("%d%d",&n,&m)) { ans=""; CL(vis,0);CL(r,0); for(int i=0;i<m;i++) { scanf("%d",&u); if(u>9)continue; vis[u]=1; } printf("Case %d: ",++ic); if(legal(n)){ printf("%d\n",n); continue; } solve(); if(ans.size()==0)puts("-1"); else cout << ans << endl; } return 0; }
hdu 4474 BFS+思维题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。