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)
              {
                    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;
}