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;
}
别人的没看太懂。。先存了吧
最新文章
- Thread基本介绍
- 服务器Linux系统安全维护基础知识介绍
- ecshop自动退出
- [转载]CSS教程:实例讲解定位Position
- Linux php 中文乱码解决
- 如何深入理解 StatsD 与 Graphite ?
- POJ 2349 Arctic Network(最小生成树,第k大边权,基础)
- MySQL导出数据文件
- android listview 重用view导致的选择混乱问题
- PHP激活用户注册验证邮箱
- Struts2中的一个类型转换示例
- SLAM+语音机器人DIY系列:(二)ROS入门——7.理解tf的原理
- Linux-共享内存通信
- Lottie 动画里有图片怎么办?设计师小姐姐也能帮你减少开发量!
- 【转载】 [unreal4入门系列之七] UE4中的Actor类和Pawn类
- JAVA_maven 配置
- GCC编译器原理(一)------GCC 工具:addr2line、ar、as、c++filt和elfedit
- Linux下安装pymysql
- 马凯军201771010116《面向对象程序设计(java)》第四周学习总结
- 虚拟 DOM