BFS-hdu-1226-超级密码

时间:2022-08-14 22:46:45

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1226

题目意思:

给一个N,给nn个jj进制的数字,问最小的不超过500位的由这些数字组成的jj进制数是十进制数N的正整数倍。

解题思路:

BFS。

因为N<=5000,所以用余数判重。

代码:

#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;
}