超级密码Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2808 Accepted Submission(s): 897Problem DescriptionIgnatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息:密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0<=N<=5000)的正整数倍(如果存在多个满足条件的数,那么最小的那个就是密码),如果这样的密码存在,那么当你输入它以后门将打开,如果不存在这样的密码……那就把门炸了吧.注意:由于宝藏的历史久远,当时的系统最多只能保存500位密码.因此如果得到的密码长度大于500也不能用来开启房门,这种情况也被认为密码不存在.Input输入数据的第一行是一个整数T(1<=T<=300),表示测试数据的数量.每组测试数据的第一行是两个整数N(0<=N<=5000)和C(2<=C<=16),其中N表示的是题目描述中的给定十进制整数,C是密码的进制数.测试数据的第二行是一个整数M(1<=M<=16),它表示构成密码的数字的数量,然后是M个数字用来表示构成密码的数字.两个测试数据之间会有一个空行隔开.注意:在给出的M个数字中,如果存在超过10的数,我们约定用A来表示10,B来表示11,C来表示12,D来表示13,E来表示14,F来表示15.我保证输入数据都是合法的.Output对于每组测试数据,如果存在要求的密码,则输出该密码,如果密码不存在,则输出"give me the bomb please".注意:构成密码的数字不一定全部都要用上;密码有可能非常长,不要试图用一个整型变量来保存密码;我保证密码最高位不为0(除非密码本身就是0).Sample Input322 1037 0 12 101125 163A B CSample Output110give me the bomb pleaseCCBHintHint
Huge input, scanf is recommended.
题意就不用讲了,是中文的.
开始做的时候没有思路.看了题解后,知道了这题 可以用同余判重来做.
我们都知道 (n+m)%mod =(n%mod+m%mod)%mod
对于这题 也可以类似得得到以下的结论
假如一个2位数 从高位到低位 依次是 ab, ;
那么 这个对这个数取模 , 相当于 (a*10+b)%mod 相当于 ((a%mod)*10+b)%mod,,这里的mod 就是n,10就是进制c.
懂了这个基本就解决这题的一半了.
然后我们要搜索, 从高位构造到低位, 不停的把高位 数取模.然后 用((a%mod)*10+b)%mod这个式子来 求 下一位的模.
而得到的任何一个模都要是最小的数得到的,因为 我们搜索的过程中 数字是从 小到大的 ,那么最先得到的余就是最好的.后面的再搜到就不用了.
last初始化为-1,只要last[i] !=-1,那么 余i 已经有过了,所以就不会再入队.这就是取余判重.
#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>using namespace std; char num[6000];// 数字 dig int last[6000];//记录之前的 如: last[i]=j i这个余的结果是下标j的数推过来得int dig[20];//输入的 可行的 数int len[6000];//记录到i这个余 数位的长度,因为题意对此有规定要 小于500void find(int tem){if(last[tem]!=0)find(last[tem]);printf("%c",num[tem]);}void bfs(int n,int c,int m){sort(dig,dig+m);queue<int> q;memset(last,-1,sizeof last);if(n==0){if(dig[0]==0) printf("0\n");else printf("give me the bomb please\n");return ; }for(int i=0;i<m;i++){if(dig[i])//第一个不能为0;{int tem=dig[i]%n;if(last[tem]==-1){q.push(tem);if(dig[i]<=9)num[tem]=dig[i]+'0';elsenum[tem]=dig[i]+'A'-10;last[tem]=0;len[tem]=1;}}}int now;while(!q.empty()){now=q.front();q.pop();if(now==0) break;if(len[now]==500){printf("give me the bomb please\n");return ;}for(int i=0;i<m;i++){int tem=(now*c+dig[i])%n;if(last[tem]==-1){last[tem]=now;if(dig[i]<=9)num[tem]=dig[i]+'0';elsenum[tem]=dig[i]+'A'-10;q.push(tem);len[tem]=len[now]+1;} } } if(now!=0){printf("give me the bomb please\n");return ;}find(0);puts("");return ;}int main(){int t,n,c;// n 的倍数 c进制int m;//m个可选数scanf("%d",&t);while(t–){scanf("%d%d",&n,&c);scanf("%d",&m);for(int i=0;i<m;i++){char tem[2];scanf("%s",tem);if(tem[0]>='0'&&tem[0]<='9')dig[i]=tem[0]-'0';elsedig[i]=tem[0]-'A'+10;}bfs(n,c,m);}return 0;}/*322 1037 0 1*/
，多对自己说“我能行，我一定可以”，
