[HDU 1226]超级密码：BFS

点击这里查看原题

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\n";
}
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\n";return;}bfs();
}
int main(){freopen("data.in","r",stdin);//ios::sync_with_stdio(false);int t;cin>>t;while(t--) solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！