BFS-hdu-1226-超級密碼

題目意思：

給一個N,給nn個jj進制的數字，問最小的不超過500位的由這些數字組成的jj進制數是十進制數N的正整數倍。

解題思路：

BFS。

因為N<=5000,所以用余數判重。

代碼：

<SPAN style="COLOR: #330033; FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/

bool vis[5500];
char save[20];
int n,jj,nn;

struct Inf
{
   string s;
   int m,len;
};

bool cmp(char a,char b)
{
   return int(a)<int(b);
}

void bfs()
{
   memset(vis,false,sizeof(vis));
   queue<Inf>myq;

   for(int i=1;i<=nn;i++)
   {
      if(save[i]=='0')
         continue;
      Inf tmp;
      tmp.s="",tmp.len=1;
      tmp.s+=save[i];
      tmp.m=((save[i]>='0'&&save[i]<='9')?(save[i]-'0'):(10+save[i]-'A'))%n;
      if(tmp.m==0) //只有一位的情況 特殊處理
      {
         cout<<tmp.s<<endl;
         return ;
      }
      vis[tmp.m]=true;
      myq.push(tmp);
   }

   while(!myq.empty())
   {
      Inf tt=myq.front();
      myq.pop();
      for(int i=1;i<=nn;i++)
      {
         int aa=(save[i]>='0'&&save[i]<='9')?(save[i]-'0'):(10+save[i]-'A');
         int t=(tt.m*jj+aa)%n;

         if(!t) //不小於2位的情況
         {
            cout<<tt.s;
            printf("%c\n",save[i]);
            return ;
         }
         if(vis[t])
            continue;
         vis[t]=true;
         Inf cur;
         cur.len=tt.len+1;
        if(cur.len>=500) //超過500位
            continue;
         cur.s=tt.s+save[i];
         cur.m=t;
         myq.push(cur);
      }
   }
   printf("give me the bomb please\n");
   return ;

}

int main()
{
   int t;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d%d",&n,&jj,&nn);
      getchar();
      //fflush(stdin); //由於這句話 ,wa了一上午
      for(int i=1;i<=nn;i++)
         scanf("%s",save+i);
      //save[nn+1]='\0';
      sort(save+1,save+nn+1,cmp);
      if(n==0)
      {
         if(save[1]=='0')
            printf("0\n");
         else
            printf("give me the bomb please\n");
         continue;
      }
      //printf("%s\n",save+1);
      bfs();
   }

   return 0;
}
</SPAN>