nyoj 密码宝盒

密码宝盒

时间限制: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;
}

别人的没看太懂。。先存了吧

上一篇:介绍一些chrome 好用的插件和快捷键


下一篇:从零开始用 Flask 搭建一个网站(三)