密码宝盒
时间限制：2000 ms | 内存限制：65535 KB
难度：3
描述
小M得到了一个宝盒，可惜打开这个宝盒需要一组神奇的密码，然而在宝盒的下面
有关于密码的提示信息：密码是一个C进制的数,并且只能由给定的M个数字中的某些构成,密码不超过500位，同时密码是一个给定十进制整数N的正整数倍,
如果这样的密码存在,那么你就可以打开宝盒并得到宝贝,如果不存在
这样的密码......那你就只能收藏这个宝盒了.
输入
输入一个T，表示有T组测试数据，(T≤500)
接下来输入N，C，M（N,C，M如上所述）( 0≤N≤5000, 1≤M≤16 , 2≤C≤16 )
然后M个数，表示密码中含有哪些数字。(输入保证合法)
用A来表示10, B来表示11, C来表示12 , D来表示13, E来表示14, F来表示15
输出
输出：密码如果存在，输入最小的那个为密码，不存在”So Sorry.”（密码不含前导零）
样例输入
3
22 10 3
7 0 1
2 10 1
1
25 16 3
A B C
样例输出
110
So Sorry.
CCB
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
//借鉴大神思路， 模拟除法算数运算可知若出现相同余数则出现循环，固可用余数标记搜索状态
//mark标记，pre为找答案记录路径，ansAt：res为i时所取得num
int mark[5005],pre[5004],ansAt[5005],N,C,M,num[20];
char ans[5005];//记录答案
char itoc(int i)
{
return i<10?(i+'0'):(i+'A'-10);
}
int ctoi(char i)
{
return i>='0'&&i<='9'?(i-'0'):(i-'A'+10);
}
bool bfs()
{
queue<int> q;
q.push(0);
while(!q.empty())
{
int temp=q.front();
q.pop();
for(int i=0;i<M;++i)
{
int res=(temp*C+num[i])%N;//余数相同即为重复搜索
if(!mark[res]&&!(!temp&&!num[i]))//注意此处temp和num同时为0时不能用余数判断
{
mark[res]=true;
ansAt[res]=num[i];
pre[res]=temp;
if(res==0)//若余数为0则可整除，找到答案
return true;
q.push(res);
}
}
}
return false;
}
bool check()
{
int temp=pre[0],i=0;
ans[i++]=itoc(ansAt[0]);
while(temp) //根据pre和ansAt构造结果
{
ans[i++]=itoc(ansAt[temp]);
temp=pre[temp];
}
ans[i]=0;
if(i<=500) //正确结果不大于500位
return true;
return false;
}
int main()
{
int T;
string str;
cin>>T;
while(T--)
{
memset(mark,false,sizeof(mark));
memset(pre,0,sizeof(pre));
cin>>N>>C>>M;
for(int i=0;i<M;++i)
{
cin>>str; //输入的可能会有16进制的字符，所以输入时定义为string类型，在转换为int型
num[i]=ctoi(str[0]); //char->int;当输入的小于10的时候，每输入一次只有一个数字，即
//也就是第一个字符str[0]，当时字母是，同理
}
sort(num,num+M); //排序为了从小到大搜索
if(N==0)
{
if(num[0]==0) //为0是要特判
cout<<'0'<<endl;
else
cout<<"So Sorry."<<endl;
continue;
}
if(bfs()&&check()) //搜到且长度合法
{
for(int i=strlen(ans)-1;i>=0;--i)
cout<<ans[i];
cout<<endl;
}
else
cout<<"So Sorry."<<endl;
}
return 0;
}
别人的没看太懂。。先存了吧