首页 > ACM题库 > HDU-杭电 > HDU 1226 超级密码-BFS-[解题报告] C++
2013
12-04

HDU 1226 超级密码-BFS-[解题报告] C++

超级密码

问题描述 :

Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息:
密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0<=N<=5000)的正整数倍(如果存在多个满足条件的数,那么最小的那个就是密码),如果这样的密码存在,那么当你输入它以后门将打开,如果不存在这样的密码……那就把门炸了吧.

注意:由于宝藏的历史久远,当时的系统最多只能保存500位密码.因此如果得到的密码长度大于500也不能用来开启房门,这种情况也被认为密码不存在.

输入:

输入数据的第一行是一个整数T(1<=T<=300),表示测试数据的数量.每组测试数据的第一行是两个整数N(0<=N<=5000)和C(2<=C<=16),其中N表示的是题目描述中的给定十进制整数,C是密码的进制数.测试数据的第二行是一个整数M(1<=M<=16),它表示构成密码的数字的数量,然后是M个数字用来表示构成密码的数字.两个测试数据之间会有一个空行隔开.

注意:在给出的M个数字中,如果存在超过10的数,我们约定用A来表示10,B来表示11,C来表示12,D来表示13,E来表示14,F来表示15.我保证输入数据都是合法的.

输出:

对于每组测试数据,如果存在要求的密码,则输出该密码,如果密码不存在,则输出"give me the bomb please".

注意:构成密码的数字不一定全部都要用上;密码有可能非常长,不要试图用一个整型变量来保存密码;我保证密码最高位不为0(除非密码本身就是0).

样例输入:

3
22 10
3
7 0 1

2 10
1
1

25 16
3
A B C

样例输出:

110
give me the bomb please
CCB

Hint
Hint
Huge input, scanf is recommended.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1226

思路:广搜,每一个状态用一个结构体来保存,记录数组的长度,然后根据长度来扩展就可以了,这里值得注意的地方余数判重以及求大数取模。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<queue>
 using namespace std;
 #define MAXN 555
 #define MAXM 5555
 struct Node{
     int num[MAXN];
     int len;
 };
 bool digit[22];
 bool mark[MAXM];
 int N,C,M;
 
 //判断C进制的密码转10进制能否被N整除
 int Judge(Node &p){
     int len=p.len,tmp=0;
     for(int i=1;i<=len;i++){
         tmp=(tmp*C+p.num[i])%N;
     }
     return tmp;
 }
 
 
 bool bfs(){
     memset(mark,false,sizeof(mark));
     queue<Node>Q;
     Node p,q;
     p.len=1;
     Q.push(p);
     while(!Q.empty()){
         p=Q.front();
         Q.pop();
         for(int i=(p.len==1?1:0);i<16;i++){
             if(digit[i]){
                 q=p;
                 q.num[q.len]=i;
                 int mod=Judge(q);
                 if(mod){
                     if(!mark[mod]&&q.len+1<=500){
                         mark[mod]=true;
                         q.len+=1;
                         Q.push(q);
                     }
                 }else {
                     for(int i=1;i<=q.len;i++){
                         printf("%X",q.num[i]);
                     }
                     puts("");
                     return true;
                 }
             }
         }
     }
     return false;
 }
 
 
 int main(){
     int _case,x;
     scanf("%d",&_case);
     while(_case--){
         scanf("%d%d%d",&N,&C,&M);
         memset(digit,false,sizeof(digit));
         for(int i=1;i<=M;i++){
             scanf("%x",&x);
             digit[x]=true;
         }
         if(N==0){
             if(digit[0])puts("0");
             else puts("give me the bomb please");
         }else if(!bfs()){
             puts("give me the bomb please");
         }
     }
     return 0;
 }

 


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  4. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  5. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;