题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1226
思路:
因为n <= 5000 ,所以方案个数也只有5000个,可以用bfs来做。。一开始挺纠结怎么做,但是上网一看别的大牛的代码,一下子就恍然大悟豁然开朗,如同拨开云雾见青天~~~^o^~~~~
代码:
#include <iostream> #include <cstdio> #include <string> #include <queue> using namespace std; const int maxn = 20; const int maxm = 5100; const int inf = (0x7f7f7f7f); int n, c, t, m; bool jud[maxn]; bool vis[maxm]; int flag; struct node { string ans; int mod; }; string res; queue<node> q; void init() { while (!q.empty()) q.pop(); memset(jud, false, sizeof(jud)); memset(vis, false, sizeof(vis)); flag = -1; res = ""; } void bfs() { int i; node now, next; for (i=1; i<16; i++) { if (jud[i]) { vis[i%n] = true; now.ans = ""; if (i < 10) now.ans = i + '0'; else now.ans = i + 'A' - 10; now.mod = i % n; q.push(now); } } while (!q.empty()) { now = q.front(); q.pop(); if (flag == 1 && (now.ans.size() > res.size())) continue; if (now.mod == 0) { if (flag == -1) { flag = 1; res = now.ans; } else { if (res.size() > now.ans.size() || (res.size() == now.ans.size() && res > now.ans)) res = now.ans; } } for (i=0; i<16; i++) { if (jud[i]) { next = now; if (i < 10) next.ans += i+'0'; else next.ans += i+'A'-10; next.mod = (now.mod * c + i) % n; if ((next.ans.size() <= 500 && vis[next.mod]==false) || next.mod==0) { vis[next.mod] = true; q.push(next); } } } } } int main() { scanf("%d", &t); while (t--) { scanf("%d %d %d", &n, &c, &m); init(); char ch[4]; for (int i=0; i<m; i++) { scanf("%s", ch); if (ch[0] >= '0' && ch[0] <= '9') jud[ch[0]-'0'] = true; else jud[ch[0]-'A'+10] = true; } if (n == 0) { if (jud[0]) puts("0"); else puts("give me the bomb please"); continue; } bfs(); if (flag == -1) puts("give me the bomb please"); else cout<<res<<endl; } return 0; }