Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3407 Accepted Submission(s): 825
题意转自：http://blog.csdn.net/yang_7_46/article/details/12356587
题意：0-9这十个数字里面的若干个数字组合出一个数，使这个数是N的倍数，求最小的这个这样的数，不存在的话输出-1。
按照数的位数BFS，从小向大枚举就可以保证构造出来的数是递增的，如果不加判断就直接搜索的话，复杂度非常高。因此需要剪枝。
优化方法：如果一个数%N==0，那么这个数就是N的倍数。在没有找到的前提下，如果A%N==B%N，而且A<B，那么其实我们就可以取A而不取B，因为如果在A末尾增加C可以使得AC%N==0，那么BC%N也等于0，易得：如果A和B追加数之后%N==0，那么最优条件下追加的数肯定相同。
因此我们只需要维护组合出来的数%N的值即可，如果在搜索的途中出现了相同的%N值，就可以直接忽略了，因为肯定没有前面的优秀。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<string>
//#include<pair>
#define N 10005
#define M 10005
#define mod 10000007
//#define p 10000007
#define mod2 100000000
#define ll long long
#define LL long long
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b)
using namespace std;
int n,ans;
int m;
int vis[15];
int pre[N];
int val[N];
void ini()
{
int x;
ans=-1;
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
while(m--){
scanf("%d",&x);
vis[x]=1;
}
}
void out(int x)
{
if(pre[x]){
out(pre[x]);
}
printf("%d",val[x]);
}
void solve()
{
int i;
queue<int> q;
for(i=1;i<=9;i++){
if(vis[i]==1) continue;
if(i>=n && i%n==0){
printf("%d\n",i);
return;
}
if(pre[i%n]!=-1) continue;
pre[i%n]=0;
val[i%n]=i;
q.push(i);
}
while(q.size()>=1)
{
int te=q.front();
int nx;
q.pop();
for(i=0;i<=9;i++){
if(vis[i]==1) continue;
nx=(te*10+i)%n;
if(nx%n==0){
out(te);
printf("%d\n",i);
return;
}
if(pre[nx]!=-1) continue;
pre[nx]=te;
val[nx]=i;
q.push(nx);
}
}
printf("-1\n");
return;
}
int main()
{
int cnt=1;
// freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
// scanf("%d",&T);
// for(int ccnt=1;ccnt<=T;ccnt++)
// while(T--)
while(scanf("%d%d",&n,&m)!=EOF)
{
//if(n==0 && k==0 ) break;
//printf("Case %d: ",ccnt);
printf("Case %d: ",cnt);
ini();
solve();
cnt++;
// out();
}
return 0;
}
HDU 4474 Yet Another Multiple Problem【2012成都regional K题】 【BFS+一个判断技巧】
原文：http://www.cnblogs.com/njczy2010/p/4008590.html