分析：这题属于隐式图搜索，状态不是非常明显，须要自己建立。
事实上搜索说白了就是暴力。
这个题目就是，首先对给出的能够组成的全部的数依次枚举。长度从小到大。
比方第一组例子，由于0不能出如今首位。那么我们枚举首位为1 和 7 看看漫步满足，
满足的话枚举第二位10 11 17 以及 70 71 77 顺便保存他们取余 n 之后的值，这样就能够剪枝，搜索过的就不用反复搜索了。
要求最早出现的BFS就可以，第一个搜到的就是。
注意长度不大于500
AC代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 15;
int a[20];
int flag[60000];
struct Node
{
string s;
int ss;
};
Node ans;
int n,c,m;
char solve(int x)
{
if(x>=0 && x<=9)
return x+'0';
return x-10+'A';
}
bool BFS()
{
memset(flag,0,sizeof(flag));
queue<Node> q;
Node now,next;
for(int i=0;i<m;i++)
{
if(a[i]!=0)
{
now.s = solve(a[i]);
now.ss = (a[i]%n);
if(now.ss == 0)
{
ans = now;
return true;
}
if(flag[now.ss]==0)
{
flag[now.ss] = 1;
q.push(now);
}
}
}
while(!q.empty())
{
now = q.front();
q.pop();
//cout<<now.s<<" "<<now.ss<<endl;
if(now.ss == 0)
{
ans = now;
return true;
}
for(int i=0;i<m;i++)
{
next.s= now.s+solve(a[i]);
next.ss = (now.ss*c+a[i])%n;
// cout<<"NEXT:"<<next.s<<" "<<next.ss<<" "<<a[i]<<endl;
if(flag[next.ss]==0)
{
flag[next.ss] = 1;
q.push(next);
}
}
}
return false;
}
int main()
{
//freopen("Input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&c,&m);
for(int i=0;i<m;i++)
{
char c[10];
scanf("%s",c);
if(c[0]>='A' && c[0]<='F')
a[i] = (c[0]-'A')+10;
else
a[i] = c[0]-'0';
}
sort(a,a+m);
if(n==0)
{
if(a[0]==0)
puts("0");
else
puts("give me the bomb please");
continue;
}
if(BFS() && ans.s.size()<=500)
cout<<ans.s<<endl;
else
puts("give me the bomb please");
}
return 0;
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。