首页 > 代码库 > 【BFS】【余数剪枝】Multiple

【BFS】【余数剪枝】Multiple

2024-10-02 13:18:39   218人阅读

[poj1465]Multiple
Time Limit: 1000MS Memory Limit: 32768K
Total Submissions: 7731 Accepted: 1723

Description

a program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple of N that has no other digits besides X1,X2..XM (if such a multiple exists).

Input

The input has several data sets separated by an empty line, each data set having the following format: 

On the first line - the number N 
On the second line - the number M 
On the following M lines - the digits X1,X2..XM.

Output

For each data set, the program should write to standard output on a single line the multiple, if such a multiple exists, and 0 otherwise. 

An example of input and output:

Sample Input

223701211

Sample Output

1100

Source

 

题目大意：给你一个在0至4999之间的数N，在给你M个数，输出这些数能组成的最小的N的倍数，没有输出0

试题分析：本体盲目搜是不可取的，因为我们根本就不知道要搜到哪里(对于DFS)，每个数的数量可以取无限多个……

              那么对于BFS来说数量还是比较多，但BFS擅长解决一些没有边界的问题嘛，所以用BFS解决此题

              那么如何剪枝呢？

              对于一个数(AX+Y)%X与(BX+Y)%X的余数是一样的，至于取谁，小的那个(也就是先搜到的那个)是我们要的，大的可以直接剪掉，所以只需要开一个数组Hash一下就好了……

               注意特判N=0的情况！！！

 

代码

#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>//#include<cmath>using namespace std;const int INF = 9999999;#define LL long longinline int read(){	int x=0,f=1;char c=getchar();	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;	return x*f;}int N,M;int a[5101];int l=1,r=1;bool flag[5101];bool fla=false;struct data{	int ga,last,ans;}Que[5101]; void print(data k){	if(k.ga!=-1){		print(Que[k.ga]);		printf("%d",k.ans);	}} void BFS(){//a当前数字 	Que[1].last=0; 	Que[1].ans=0;	Que[1].ga=-1; 	int l1,p;	while(l<=r){		l1=Que[l].last;		for(int i=1;i<=M;i++){			p=(l1*10+a[i])%N;			if(!flag[p]&&(Que[l].ga!=-1||a[i]>0)){				flag[p]=true;				Que[++r].ans=a[i];				Que[r].ga=l;				Que[r].last=p;				if(p==0){					data s=Que[r];					print(s);					printf("\n");					fla=true;					return ;				}			}		}		l++;	}}int main(){	//freopen(".in","r",stdin);	//freopen(".out","w",stdout);	while(scanf("%d",&N)!=EOF){		M=read();		for(int i=1;i<=M;i++) a[i]=read();		sort(a+1,a+M+1);		if(N==0){			puts("0");			continue;		}		memset(flag,false,sizeof(flag));		l=r=1;		fla=false;		BFS();		if(!fla){			puts("0");		}	}	return 0;}

【BFS】【余数剪枝】Multiple


联系
我们