hdu 1226 超级密码 bfs+取余判重

Huge input, scanf is recommended.

题意就不用讲了,是中文的.

开始做的时候没有思路.看了题解后,知道了这题 可以用同余判重来做.

我们都知道 (n+m)%mod =(n%mod+m%mod)%mod

对于这题 也可以类似得得到以下的结论

假如一个2位数  从高位到低位 依次是 ab,  ;

那么 这个对这个数取模  , 相当于 (a*10+b)%mod 相当于 ((a%mod)*10+b)%mod,,这里的mod 就是n,10就是进制c.

懂了这个基本就解决这题的一半了.

然后我们要搜索,  从高位构造到低位, 不停的把高位 数取模.然后 用 ((a%mod)*10+b)%mod这个式子来 求 下一位的模.

而得到的任何一个模都要是最小的数得到的,因为 我们搜索的过程中 数字是从 小到大的 ,那么最先得到的余就是最好的.后面的再搜到就不用了.

last初始化为-1,只要last[i] !=-1,那么 余i 已经有过了,所以就不会再入队.这就是取余判重.

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std; 

char num[6000];// 数字 dig 
int last[6000];//记录之前的 如: last[i]=j   i这个余的结果是下标j的数推过来得
int dig[20];//输入的 可行的 数
int len[6000];//记录到i这个余 数位的长度,因为题意对此有规定要 小于500  
 
void find(int tem)
{
	if(last[tem]!=0)
		find(last[tem]);
	printf("%c",num[tem]);
}
void bfs(int n,int c,int m)
{
	sort(dig,dig+m);
	queue<int> q;
	memset(last,-1,sizeof last);
	if(n==0)
	{
		if(dig[0]==0) printf("0\n");  
        else printf("give me the bomb please\n");  
        return ;  
	}


	for(int i=0;i<m;i++)
	{
		if(dig[i])//第一个不能为0;
		{
			int tem=dig[i]%n;
			if(last[tem]==-1)
			{
				q.push(tem);
				if(dig[i]<=9)
					num[tem]=dig[i]+'0';
				else
					num[tem]=dig[i]+'A'-10;
				last[tem]=0;
				len[tem]=1;
			}
		}
	}

	int now;
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		if(now==0) break;
		if(len[now]==500)
		{
			printf("give me the bomb please\n");  
			return ;
		}

		for(int i=0;i<m;i++)
		{
			int tem=(now*c+dig[i])%n;
			if(last[tem]==-1)
			{
				last[tem]=now;
				if(dig[i]<=9)
					num[tem]=dig[i]+'0';
				else
					num[tem]=dig[i]+'A'-10;
				q.push(tem);
				len[tem]=len[now]+1;
			} 
		} 
	} 
	if(now!=0)
	{
		printf("give me the bomb please\n");  
		return ;
	}
	find(0);
	puts("");
	return ;
}



int main()
{
	int t,n,c;// n 的倍数  c进制
	int m;//m个可选数
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&c);
		scanf("%d",&m);


		for(int i=0;i<m;i++)
		{
			char tem[2];
			scanf("%s",tem);
			if(tem[0]>='0'&&tem[0]<='9')
				dig[i]=tem[0]-'0';
			else
				dig[i]=tem[0]-'A'+10;
		}
		bfs(n,c,m);
	}
	return 0;
}
/*


3
22 10
3
7 0 1

*/

hdu 1226 超级密码 bfs+取余判重

原文：http://blog.csdn.net/u013532224/article/details/43567643