HDU 4474&&POJ 1465 BFS&&余数判重
来源：程序员人生 发布时间：2014-11-10 08:42:19 阅读次数：1825次
两道题只是输入输出格式略有不同
给出n，m，m个数
要求生成1个数x，是n的倍数，并且只由这M个数构成（或不能含有这M个数中的任意1个），求最小的x，没有则输出⑴（0）；
BFS找每个满足n的倍数的数，用余数判重优化
对给定两个数A，B，如果A和B模N都相同，设为C，即：
A=x*N+C
B=y*N+C
那末如果在A后面加上1个数字能够被N整除，则在B后面加上这个数字也肯定可以被N整除
即：(A*10+X)%N==(B*10+X)%N
因此可以利用模N的结果进行判重，只保存相同余数的最小数，因而采取BFS搜索
HDU4474：
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
int hash[11],num[10010],pre[10010];
int n;
void pri(int k)
{
if (pre[k]!=⑴) pri(pre[k]);
printf("%d",num[k]);
}
void bfs()
{
queue<int>q;
int i,cur,next;
for (i=1;i<=9;i++)
if(hash[i]==0)
{
cur=i%n;
if (cur==0) { printf("%d
",i); return ;}
num[cur]=i;
q.push(cur);
}
while (!q.empty())
{
cur=q.front();
q.pop();
for (i=0;i<=9;i++)
if(hash[i]==0)
{
next=(cur*10+i)%n;
if (num[next]==⑴)
{
q.push(next);
num[next]=i;
pre[next]=cur;
}
if (next==0) {pri(next); printf("
"); return ;}
}
}
printf("⑴
");
return ;
}
int main()
{
int m,x,Case=1;
while (scanf("%d",&n)!=EOF)
{
memset(hash,0,sizeof(hash));
memset(num,⑴,sizeof(num));
memset(pre,⑴,sizeof(pre));
scanf("%d",&m);
while (m--)
{
scanf("%d",&x);
hash[x]=1;
}
printf("Case %d: ",Case++);
if(n==0) { printf("⑴
"); continue;}
bfs();
}
return 0;
}
POJ1465：
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
int hash[11],num[10010],pre[10010];
int n;
void pri(int k)
{
if (pre[k]!=⑴) pri(pre[k]);
printf("%d",num[k]);
}
void bfs()
{
queue<int>q;
int i,cur,next;
for (i=1;i<=9;i++)
if(hash[i]==1)
{
cur=i%n;
if (cur==0) { printf("%d
",i); return ;}
num[cur]=i;
q.push(cur);
}
while (!q.empty())
{
cur=q.front();
q.pop();
for (i=0;i<=9;i++)
if(hash[i]==1)
{
next=(cur*10+i)%n;
if (num[next]==⑴)
{
q.push(next);
num[next]=i;
pre[next]=cur;
}
if (next==0) {pri(next); printf("
"); return ;}
}
}
printf("0
");
return ;
}
int main()
{
int m,x,Case=1;
while (scanf("%d",&n)!=EOF)
{
memset(hash,0,sizeof(hash));
memset(num,⑴,sizeof(num));
memset(pre,⑴,sizeof(pre));
scanf("%d",&m);
while (m--)
{
scanf("%d",&x);
hash[x]=1;
}
// printf("Case %d: ",Case++);
if(n==0) { printf("0
"); continue;}
bfs();
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
