HDU 1226超级密码(数位BFS)

HDU 1226超级密码(数位BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1226

Problem Description

Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息:

密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0<=N<=5000)的正整数倍(如果存在多个满足条件的数,那么最小的那个就是密码),如果这样的密码存在,那么当你输入它以后门将打开,如果不存在这样的密码......那就把门炸了吧.

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

Input

输入数据的第一行是一个整数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.我保证输入数据都是合法的.

Output

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

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

Sample Input

3

22 10

3

7 0 1

2 10

1

1

25 16

3

A B C

Sample Output

110

give me the bomb please

CCB

分析：其实本题就是POJ1456的加强版，多了个C进制。

http://blog.csdn.net/u013480600/article/details/26458435

首先由于此数只能由给定的M位数位构成，所以我们依然用BFS来从0构成所有可能的长C进制整数。（如果N==0，直接特殊处理。只要N！=0，那么它的倍数肯定不为0）

BFS的时候节点状态我们这么设计：

struct Node

{

int digit;//当前状态的个位值

int r;//当前状态值%N的余数

int pre;//当前状态的个位值的连接指针,用来找到所有当前状态的位

int dist;//表示当前数字一共有dist位，不过这里我们只有个位digit，之前的//dist-1位都是通过pre链接的。

}Q[maxn];

下面依然是剪枝细节了，如果我们当前构造了一个长整数a%N==3(且我们检测了a的所有后继)，那么我们之后构造的任何长整数b%N==3，这样的b我们可以直接抛弃不用管b且不用构造b的后继了。

因为（a*C+i）%N == （b*C+i）%N,所以如果b的某个后继%N==0的话,那么a的对应位构造的后继也能%N==0的.且a的后继肯定比b对应的后继小,所以需要抛弃b.

具体细节体会代码. 本来很快就写完了,结果忘了加<=500长度的条件结果错了,然后我写了个Pyhton生成随机数据的代码,和别人的数据比较了,都一样,才想起来长度<=500位.

当然本题还有另外一种做法,时间和空间需要都大很多,就是每个状态节点直接保存500位int或char数组然后BFS.

AC代码: 15ms

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=50000;
int N,C,M;
int digit[20];      //题目给的最低位数
bool flag[5000+1000];
struct Node
{
    int digit;
    int r;
    int pre;
    int dist;
    Node(){}
    Node(int digit,int r,int pre,int dist):digit(digit),r(r),pre(pre),dist(dist){}
}Q[maxn];
int BFS()
{
    memset(flag,0,sizeof(flag));
    int front=0,tail=1;
    Q[front]=Node(0,0,-1,0);
    while(front<tail)
    {
        Node node =Q[front];
        for(int i=0;i<M;i++)
        {
            int nr=(node.r*C+digit[i])%N;
            if(!flag[nr] && (node.pre!=-1 || digit[i]!=0) && node.dist+1<=500) //错误,忘了加<=500条件
            {
                flag[nr]=true;
                Q[tail++]=Node(digit[i],nr,front,node.dist+1);//错误,上面front++了,这里构造Node还用front
                if(nr==0) return tail-1;
            }
        }
        front++;
    }
    return -1;
}
void print(int i)
{
    if(i)
    {
        print(Q[i].pre);
        printf("%c",Q[i].digit<=9?Q[i].digit+'0':Q[i].digit-10+'A');
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("2.txt", "w", stdout);
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&N,&C,&M);
        for(int i=0;i<M;i++)
        {
            char x;
            scanf(" %c",&x);    //注意%c前面的空格
            if(x>='A'&&x<='Z') digit[i]=x-'A'+10;
            else digit[i]= x-'0';
        }
        sort(digit,digit+M);                    //错误,这里忘了排序
        if(N==0)
        {
            if(digit[0]==0) printf("0\n");
            else printf("give me the bomb please\n");
            continue;
        }
        int ans=BFS();
        if(ans==-1) printf("give me the bomb please\n");
        else print(ans),puts("");

    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Pyhton 生成测试数据的代码:

import random


T = 50 #50个实例
print T
for i in range(T):
    N= random.randint(0,5000)
    C=random.randint(2,16)
    digit=[0 for k in range(20)]
    for j in range(C):
        a=random.randint(0,C-1)
        if a <=9 :
            digit[j]= a
        elif a==10:
            digit[j]= 'A'
        elif a==11:
            digit[j]='B'
        elif a==12:
            digit[j]='C'
        elif a==13:
            digit[j]='D'
        elif a==14:
            digit[j]='E'
        elif a==15:
            digit[j]='F'
    new_digit = list(set(digit))
    print N,' ',C
    print len(new_digit)
    for j in range(len(new_digit)):
        print new_digit[j],
    print 
    print