超级密码(bfs).cpp

杭电acm解题报告2001---2099.

//密码很大部分是重复的，可以不弹出队列，做一个链接以便回溯
//hash值依据余数，因为如果该余数产生过，当然是越小越好，则后续同余密码不用扩展
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int t,n,c,m;
int dig[20];
bool hash[5100];
struct node {//num选择的值，pre前一个节点位置，mod密码余数，len密码长度
	int num, pre, mod, len;
};
node SQ[100000];
int top,end;

int bfs()
{
	int l,i,j;
	top = end = 0;
	memset(hash,0,sizeof(hash));
	for (i=0;i<m;i++) {
		if (dig[i] != 0) {
			SQ[end].len = 1;
			SQ[end].pre = -1;
			SQ[end].num = dig[i];
			SQ[end].mod = dig[i] % n;
			hash[ SQ[end].mod ] = true;
			if (dig[i] % n == 0) {
				return end;
			}
			end ++;
		}
	}
	
	while (top < end) {
		node now = SQ[top ++];
		if (now.len > 500) {
			return -1;
		}
		for (i=0;i<m;i++) {
			SQ[end] = now;
			SQ[end].len ++;
			SQ[end].num = dig[i];
			SQ[end].pre = top - 1;
			SQ[end].mod = (SQ[end].mod * c + dig[i]) % n;
			if (!hash[SQ[end].mod] && SQ[end].len <= 500) {
				hash[SQ[end].mod] = true;
				if (SQ[end].mod == 0) {
					return end;
				}
				end ++;
			}
		}//for
	}
	return -1;
}

int main()
{
	int i,j,len;
	char str[5];
	char ans[510];
	
	scanf("%d",&t);
	while (t --) {
		scanf("%d %d %d",&n,&c,&m);
		for (i=0;i<m;i++) {
			scanf("%X",&dig[i]);
		}
		sort(dig, dig+m);
		if (n == 0) {
			if (dig[0] != 0) {
				printf("give me the bomb please\n");
			}
			else {
				printf("0\n");
			}
		}
		else {
			int pos = bfs();
			if (pos == -1) {
				printf("give me the bomb please\n");
			}
			else {
				len = 0;
				while (pos != -1) {
					if (SQ[pos].num < 10) {
						ans[len ++] = SQ[pos].num + '0';
					}
					else {
						ans[len ++] = SQ[pos].num - 10 + 'A';
					}
					pos = SQ[pos].pre;
				}
				ans[len] = 0;
				reverse(ans,ans+len);
				printf("%s\n",ans);
			}
		}//if n
	}
}