HDU 4474&&POJ 1465 BFS&&余數判重
來源：程序員人生 發布時間：2014-11-10 08:42:19 閱讀次數：2018次
兩道題只是輸入輸出格式略有不同
給出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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
