学步园

  题意是： 给出一个 0 - 4999 的数 N  ，在给出 M 个0-9的数，判断这M个数字能不能构成一个数是N的倍数，如果有输出最小的，如果没有输出0。

此题用BFS 。。 这个题好在 用 余数判重剪枝。。 

 

BFS  如果不加以剪枝，一定会搜索的情况会很庞大。所以应该用余数判重 。

   为什么可以用余数判重？

       A=a*N +e 即A%N =e

       B= b*N+e即B%N=e

      当A  B mod N的余数相同时，如果先出现A 。

      在A  后加上一个数 i 时 ，  新的数   C = 10 *a*N + 10 *e+i;

      同样  B后加上数 i 时 ， D = 10*b*N +10*e+i;    由于C D 前边 10*a*N 和 10*b*N 都是N的倍数 ，则C D mod N 的余数都是有 10*e+i 决定的。

    于是 C D  mod N 同余。

    因此 A B 同余 都添加上 i 之后 新的两个数C D也是同余的。在无论添加多少个数，新生成的两个数也是同余的。因此 在A 之后如果不出现 N的倍数 ，则

在B之后也不会出现。 在A 之后出现，那B之后也会出现。  有因为要求求最小值。所以只需要搜索min（A,B）之后的 ，对于另外一个数之后就不用搜索了。

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define LL long long
#define inf 0x7fffffff
#define eps 1e-7
#define N 5509
#define M 20009
using namespace std;
int T,n,m,k;
struct Node
{
    LL v;
    int w;
    int pre;
} a[N];
int h[100];
int vis[N];
void print(int x)
{
    if(x)
    {
        print(a[x].pre);
        printf("%d",a[x].w);
    }
}
void bfs()
{
    int l=0,r=1;
    a[0].pre=a[0].w=a[0].v=0;
    while(l<r)
    {
        Node t;
        t=a[l];
        t.pre=l++;
        int v=t.v;
        for (int i=0; i<m; ++i )
        {
            int x=(v*10+h[i])%n;//n不能是0，Float-Point Error
            if(x==0&&l!=1)
            {
                print(t.pre);
                printf("%d\n",h[i]);
                return ;
            }
            if(vis[x]||(l==1&&h[i]==0))continue;
            vis[x]=1;
            t.v=x;
            t.w=h[i];
            a[r++]=t;
        }
    }
    printf("0\n");
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("ex.in","r",stdin);
#endif
    int ncase=0;
    while (scanf("%d%d",&n,&m)==2)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0; i<m; ++i)
        {
            scanf("%d",&h[i]);
        }
        if (n==0)//
        {
            printf("0\n");
            continue;
        }
        sort(h,h+m);
        bfs();
    }
    return 0;
}