[HDU 1226]超级密码：BFS

2019-04-14 12:12发布

站内文章 / 模拟电子
18015 0 941
点击这里查看原题 n只有5000，设vis[i]表示模n为i的最小的c进制数（在代码里，vis[i]表示模n为i的数是否已出现），可以用BFS来求解，若位数大于500或该余数已出现过，则不再加入队列，找出最小的模n为0的数即为答案。 /* User:Small Language:C++ Problem No.:1226 */ #include #define ll long long #define inf 999999999 using namespace std; string s="0123456789ABCDEF"; int n,c,m; bool vis[5005],di[16]; struct num{ int len,c[505]; }; int cal(num a){ int l=a.len,tmp=0; for(int i=1;i<=l;i++) tmp=(tmp*c+a.c[i])%n; return tmp; } void write(num p){ for(int i=1;i<=p.len;i++) cout<cout<void bfs(){ memset(vis,0,sizeof(vis)); queue q; for(int i=1;i<16;i++){ if(di[i]==0) continue; num tmp; tmp.len=1; tmp.c[1]=i; int k=cal(tmp); if(k==0){ write(tmp); return; } else{ vis[k]=1; q.push(tmp); } } while(!q.empty()){ num now=q.front(); q.pop(); for(int i=0;i<16;i++){ if(di[i]==0) continue; num tmp=now; tmp.c[++tmp.len]=i; int k=cal(tmp); if(k==0){ write(tmp); return; } else{ if(!vis[k]&&tmp.len<=500){ vis[k]=1; q.push(tmp); } } } } cout<<"give me the bomb please "; } void solve(){ memset(di,0,sizeof(di)); cin>>n>>c>>m; for(int i=1;i<=m;i++){ char num; cin>>num; di[num>='A'?(num-'A'+10):num-'0']=1; } if(n==0){ if(di[0]==1) cout<<0<else cout<<"give me the bomb please "; return; } bfs(); } int main(){ freopen("data.in","r",stdin);// ios::sync_with_stdio(false); int t; cin>>t; while(t--) solve(); return 0; }

热门文章