hdu 1226 超级密码

这题算中等题吧...还是算有一定难度的入门题...

最重要的就是用了取余的剪枝来进行优化;不采用取余的话会MLE的..

所有值都可以看做一个和 0 ~ N-1 有对应的映射关系;

所以记录下最先出现过的在 0 ~ N-1 的值 (当然要取余) , 碰到余数相同的就跳过 ;

感谢大牛的代码分享 : http://m.blog.csdn.net/blog/lfglfglfglfg/39210905 //找不到添加网页的东东..

　　　　　　　　　　http://blog.csdn.net/libin56842/article/details/9750901 这个的讲解比较详细,两者内容差不多;

  1 #include<iostream>
  2 #include<string>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cstring>
  6 using namespace std;
  7 int N, C, M;
  8 string s = "ABCDEF";
  9 char num[16];
 10 int numm[16];
 11 int visit[5005];
 12 struct Node{
 13     int a[505];
 14     int len;
 15 };
 16 //输出
 17 void print(Node nod){
 18     for (int i = 0; i<nod.len; i++){
 19         if (nod.a[i]<10)
 20             cout << nod.a[i];
 21         else 
 22             cout << s[nod.a[i] - 10];
 23     }
 24     cout << endl;
 25 }
 26 //对该数对N取余;
 27 int mod(Node nod){
 28     int ret = 0;
 29     for (int i = 0; i<nod.len; i++){
 30         ret = (ret*C + nod.a[i]) % N;
 31     }
 32     return ret;
 33 }
 34 
 35 int bfs(){
 36     queue<Node> q;
 37     Node node;
 38     int r;
 39     memset(visit, 0, sizeof(visit));
 40     //初始化队列内元素
 41     for (int i = 0; i<M; i++){
 42         if (i == 0 && numm[0] == 0) 
 43             continue;
 44         node.len = 1;
 45         node.a[0] = numm[i];
 46         r = mod(node);
 47         if (r == 0){
 48             print(node);
 49             return 1;
 50         }
 51         if (!visit[r]){
 52             visit[r] = 1;
 53             q.push(node);
 54         }
 55     }
 56 
 57     while (!q.empty()){
 58         node = q.front();
 59         q.pop();
 60         for (int i = 0; i<M; i++){
 61             if (node.len>500)
 62             {
 63                 return 0;
 64             }
 65             node.a[node.len] = numm[i];
 66             node.len++;
 67             r = mod(node);
 68             if (r == 0){
 69                 print(node);
 70                 return 1;
 71             }
 72             if (!visit[r]){
 73                 visit[r] = 1;
 74                 q.push(node);
 75             }
 76             node.len--;//已经检查过了,没必要push,长度不增加;
 77         }
 78     }
 79     return 0;
 80 }
 81 int main(){
 82     int t;
 83     cin >> t;
 84     while (t--){
 85         cin >> N >> C >> M;
 86         for (int i = 0; i<M; i++)
 87             cin >> num[i];
 88         sort(num, num + M);
 89         for (int i = 0; i<M; i++){
 90             if (num[i] - '0'<10){
 91                 numm[i] = num[i] - '0';
 92             }
 93             else {
                         numm[i] = 10 + num[i] - 'A'; 
                    }
 94         }
 95         if (N){
 96             if (!bfs())cout << "give me the bomb please" << endl;
 97         }
 98         else {
 99             if (numm[0] == 0) 
                       cout << 0 << endl;
100             else  
                      cout << "give me the bomb please" << endl;
101         }
102 
103     }
104 }