HDU 1226 超级密码| NYOJ 929 密码宝盒

超级密码

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3344 Accepted Submission(s): 1069

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

Sample Output

110
give me the bomb please
CCB

Hint
Hint
 
Huge input, scanf is recommended.

一开始居然想的是大整数的处理方法，毕竟10s，也是一种诱惑- -

不过后来发现这个明显是一个BFS的题目。

对每个位置进行BFS入队。在结构体中保存路径。以k mod n = r => ( k * p + a ) ( mod n) = ( r * p + a ) ( mod n ) 的余数作为大整数的映射。当出现大整数位树大于500，或者之前已经访问过相同的余数的时候，说明已经无解了。当然在处理新的头的时候，一定要注意不能是0。每次记得存储路径就完事了

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>

using namespace std ;
int N, M, C, T;
int letter[20];
bool vis[5001];

struct node{
    int a;
    int b[505];
    int num;
    int step;
};

bool bfs(){
    queue<node>q;
    node head, tail;
    memset(vis, false, sizeof(vis));
    head.a = 0;
    head.num = 0;
    head.step = 0;
    q.push(head);

    while(!q.empty()){
        head = q.front();
        q.pop();
        for(int i = 0; i < M; i ++){
            tail.a = head.a * C + letter[i];
            if(!tail.a)
                    continue;
            tail.step = head.step + 1;
            tail.num = head.num +1;
            tail.a = tail.a % N;
            if(vis[tail.a] || tail.num > 500)
                continue;
            vis[tail.a] = true;
            for(int j = 0; j < head.num; j ++){
                tail.b[j] = head.b[j];
            }
            tail.b[head.num] = letter[i];
            if(!tail.a){
                for(int j = 0; j < tail.num; j ++){
                    if(tail.b[j] > 9)
                        printf("%c", tail.b[j] + 'A' - 10);
                    else
                        printf("%d", tail.b[j]);
                }
                printf("
");
                return true;
            }
            q.push(tail);
        }
    }
    return false;
}

int main(void){
    char c;
    scanf("%d", &T);
    while(T --){
        scanf("%d%d%d", &N, &C, &M);
        for(int i = 0; i < M; i ++){
            getchar();
            scanf("%c", &c);
            if(c >= 'A' && c <= 'F')
                letter[i] = c - 55;
            else
                letter[i] = c - '0';
        }
        sort(letter,letter + M);
        if(!N){
            if(!letter[0])
                printf("0
");
            else
                printf("give me the bomb please
");
            continue;
        }

        if(!bfs())
            printf("give me the bomb please
");
    }
    return 0;
}