题意：略过
分析：用m个数字组成一个能够被n整除的c进制数的最小值，实际上本题的关键就在于这个最小值上。
首先确定我们的思路是从小到大寻找。先查看一位数，即查看着m个数字是否能被n整除；若不能，就查看任意可能的两位数组合...可是如此一来，预算量太大。于是我们考虑是否存在冗余量。
已知A,B两个数（A<B），A%n==x，B%n==x，我们称其为同余，那么以它们为基础的相同变换（从一位数到两位数）：A*c+C，B*c+C，这两个数同样同余，(A*c+C)%n==((A*c)%n+C%n)%n==(((A%n)*c)%n+C%n)%n==(((B%n)*c)%n+C%n)%n==(B*c+C)%n。所以，若我们能够在由 B 为基础扩展出的数字中找到一个能被 n 整除的值，那经过相同的变换，由 A 扩展出的数字一定也能被 n 整除，并且一定更小。
根据以上推论，我们知道一旦我们发现一个余数为x的数字（因为是从小到大查找，该数字必然是最小值），那么之后凡是余数为x的数字都可以忽略不计。由于题目中给出的数字n<=5000，所以我们用bfs搜索，最多只需查找5000个状态，计算量大幅减少。
错误：n==0，当且仅当m个数字中含有0，答案为0；否则，无解。
注意：本题是pku 1465的延伸——由10进制数改为任意进制数，但是时限过于宽泛（也可能是数据太水了），导致用这道题的思路解题严重超时。
这是最初的思路，把每一个扩展的数字都加入队列，运算量太大。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=;
const int N=; struct Node{
char s[MAXN];
int len;
}; int md[MAXN];
int num[N];
int n,c,m;
queue<Node>q; int Num(char ch)
{
if(ch>=''&&ch<='')
return ch-'';
return ch-'A'+;
} int qmod(Node e)
{
int cnt=;
for(int i=;i<e.len;i++)
cnt=(cnt*c+e.s[i])%n;
return cnt;
} void print(Node e)
{
for(int i=;i<e.len;i++)
if(e.s[i]>=&&e.s[i]<=)
printf("%d",e.s[i]);
else
printf("%c",e.s[i]-+'A');
printf("\n");
} int bfs()
{
memset(md,,sizeof(md));
while(!q.empty())
q.pop(); Node e;
for(int i=;i<;i++)
{
if(num[i]){
e.s[]=i;
e.len=;
int cnt=qmod(e);
if(cnt==){
print(e);
return ;
}
if(!md[cnt]){
q.push(e);
md[cnt]=;
}
}
}
while(!q.empty())
{
e=q.front();q.pop();
/*
for(int i=0;i<e.len;i++)
printf("%d",e.s[i]);
printf("\n");
*/
for(int i=;i<;i++)
{
if(num[i]){
e.s[e.len]=i;
e.len++;
if(e.len>=)
return -; int cnt=qmod(e);
if(cnt==){
print(e);
return ;
}
if(!md[cnt]){
q.push(e);
md[cnt]=;
}
e.len--;
}
}
}
//printf("??\n");
return -;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&c,&m); memset(num,,sizeof(num));
for(int i=;i<m;i++)
{
char x[];
scanf("%s",x);
num[Num(x[])]=;
}
if(n==)
if(num[])
printf("0\n");
else
printf("give me the bomb please\n");
else{
int ans=bfs();
if(ans==-)
printf("give me the bomb please\n");
}
}
return ;
}
做完pku 1465 后，又回过头来做，忘记加密码长度的限制 len<=500，狠狠的wa了一发
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=;
const int N=; struct Node{
int pre;
int r;
int d;
int len;
}; int vis[MAXN];
int num[N];
int n,c,m;
Node q[MAXN]; int Num(char ch)
{
if(''<=ch&&ch<='')
return ch-'';
return ch-'A'+;
} void print(int x)
{
if(q[x].pre==-)
return ;
print(q[x].pre);
if(q[x].d>=)
printf("%c",q[x].d-+'A');
else
printf("%d",q[x].d);
} int bfs()
{
memset(vis,,sizeof(vis));
int dl,dr;
dl=dr=;
Node u,v;
u.pre=-;
u.d=;
u.r=;
u.len=;
q[dr++]=u;
vis[]=; int ok=;
while(dl<dr)
{
u=q[dl++];
for(int i=;i<m;i++)
{
int r=u.r*c+num[i];
if(r>=n&&r%n==){
print(dl-);
if(num[i]>=)
printf("%c\n",num[i]-+'A');
else
printf("%d\n",num[i]);
return ;
}
r=r%n;
if(!vis[r]){
vis[r]=;
v.r=r;
v.d=num[i];
v.pre=dl-;
v.len=u.len+;
if(v.len>)
return -;
q[dr++]=v;
}
}
}
return -;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&c,&m);
memset(num,-,sizeof(num));
for(int i=;i<m;i++)
{
char s[];
scanf("%s",s);
num[i]=Num(s[]);
}
sort(num,num+m); if(n==)
if(num[]==)
printf("0\n");
else
printf("give me the bomb please\n");
else{
int ans=bfs();
if(ans==-)
printf("give me the bomb please\n");
}
}
return ;
}