HDOJ - 4474 简单分析后,BFS

若k=a*10+b...那么k%m=(a*10)%n+b%n...利用这个性质就可以BFS了...一位一位的搜...

当出现对n取余为0...则找到答案...

由于n最大为10000,而搜的时候,每个余数之考虑其第一个存在的数(最小的)..所以时间上完全ok....

Program:

[cpp]
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000007
#define MAXN 10005
using namespace std;
struct node
{
      string s;
      int m;
};
string ans;
bool f[12],used[MAXN];
int n;
queue<node> myqueue;
void BFS()
{
      int i;
      node h,p;
      ans="-1";
      memset(used,false,sizeof(used));
      while (!myqueue.empty()) myqueue.pop();
      for (i=1;i<=9;i++)
        if (f[i] && !used[i%n])
        {
              h.m=i%n;
              h.s=i+'0';
              myqueue.push(h);
              used[h.m]=true;
              if (h.m==0)
              {
                    ans=h.s;
                    return;
              }
        }
      while (!myqueue.empty())
      {
              h=myqueue.front();
              myqueue.pop();
              for (i=0;i<=9;i++)
              if (f[i] && !used[(h.m*10+i)%n])
              {
                    p.m=(h.m*10+i)%n;
                    p.s=h.s+char(i+'0');
                    myqueue.push(p);
                    used[p.m]=true;
                    if (p.m==0)
                    {
                           ans=p.s;
                           return;
                    }
              }
      }
      return;
}
int main()
{
      int m,x,t=0;
      while (~scanf("%d",&n))
      {
             memset(f,true,sizeof(f));
             scanf("%d",&m);
             while (m--)
             {
                    scanf("%d",&x);
                    f[x]=false;
             }
             BFS();
             printf("Case %d: %s\n",++t,ans.c_str());
      }
      return 0;
}

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000007
#define MAXN 10005
using namespace std;
struct node
{
      string s;
      int m;
};
string ans;
bool f[12],used[MAXN];
int n;
queue<node> myqueue;
void BFS()
{
      int i;
      node h,p;
      ans="-1";
      memset(used,false,sizeof(used));
      while (!myqueue.empty()) myqueue.pop();
      for (i=1;i<=9;i++)
        if (f[i] && !used[i%n])
        {
              h.m=i%n;
              h.s=i+'0';
              myqueue.push(h);
              used[h.m]=true;
              if (h.m==0)
              {
&n

补充：软件开发 , C++ ,