密码宝盒
时间限制: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;
}
别人的没看太懂。。先存了吧