SDUTOJ2165 Crack Mathmen(模拟,哈希表,快速幂)

题目连接:传送门

        这1题是我们昨天省赛集训的题目,我可给坑惨了。不过所幸没有给白坑,学到了1些东西。最有感触的是这个

for(int i = 0 ; i < strlen(str); i++) //危险,切勿模仿

如果数组大1些,这样写就直接超时。我之前找了好久都没发现,最后学长告知我把他写成这样

int len = strlen(str);
for(int i = 0 ; i < len; i++)

为何呢?缘由是如果数组较大的话,那末就要计算 strlen(str)次的str的长度,这样会致使超时。但是如果将其保存在1个整型变量中,那末就只要计算1次str的长度就行了。这样就不会超时了。感觉自己瞬间就涨姿式了,之前多是由于数组比较小,完全没有注意到这个,这1次数组大了1些,我可是吃尽了苦头。大家切记啊,不然准备好1晚上的时间来查错吧。

       哈希表听起来是否是很高大上啊,用了这么久,现在才知道那玩意叫哈希表。不过哈希表的确是个好东西,他可使你的查找时间是 O(1) ,为何呢?由于他1次就能够找到了。我来讲说哈希表吧,你1看,你就猛然1惊,怎样是这玩意。

哈希表(文字版):

       在很多数据结构中(线性表,树等),记录在结构中的相对位置是随机的,和记录的关键字之间不存在肯定关系,因此在结构中查找记录时,需要进行1系列和关键字的比较。这1类查找方法建立在比较的基础上,所以其查找的效力依赖于比较的次数。理想情况固然是不经任何比较,1次就得出结果。那就必须在记录的存储位置和他的关键字之间建立1个肯定的对应关系 f ,使每个关键字和结构中1个唯1的贮存位置相对应。因此在查找时只要根据这个对应关系 f 就能够找到定值
K的像 f (K
)。若结构中存在关键字与K相等的记录,则一定在 f(k)的贮存位置上,所以我们1次就能够找到记录。我们称这个为 哈希函数。我们在使用中常常使用打表法与之结合,所以哈希表就诞生了。

哈希表(表达式版): f(key1) = key2 (这个表达式不是固定,我想说的重点是建立1个映照关系,不管你的表达式是1次函数,还是2次,3次都行,这个根据需要来变化)

――――――――――――――――――――分割线――――――――――――――――――

        瞎扯了很多,我们现在来看看题。题目想要你做的就是将1串密文还原。对本题,由于还有1个 n 次方的问题 所以我们又要用到 快速幂 。不知道快速幂的请移步:这里

这1题我们可以这样处理,摹拟他的加密方式将,他所用到的字符都进行加密,将其全部存起来,然后我们根据密文1个个的比较,比较时我们就能够使用哈希表,来提高效力。固然不使用这1题好像也能过,不过时间上那就……。所以我们还是用1下哈希表,这样快1些也方便。最后我们再将题目的细节处理1下这1题就完成了。对 No Solution的情况,斟酌1下,第1是将多解的删去,然后包括不使用的字符(在本题也就是除 字母和数字之外的字符) 也删去。这1题就大美满了。

代码以下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 997
#define MAXN 1000000 + 100
struct N{
int x;
char c;
}List_char[62]; //用结构体将字符,与其对应的加密后的文本存进结构体数组
char str[MAXN],Outstr[MAXN/3]; //str为输入文本,Outstr为输出文本
int ASC[MAXN/3],Hash[997],flog; //ASC存每一个字母的加密文本,Hash为加密的密文与其数组下标的哈希表
int mod_pow(int x, int n){ //快速幂
int res = 1;
while( n > 0 ){
if( n & 1 ) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}

int cmp(const void* a, const void* b){
struct N* A = (struct N*)a;
struct N* B = (struct N*)b;
if(A->x == B->x)
flog = 1; //如果存在多解,这flog = 1
return A->x – B->x;
}
int main(){
int T, n, len;
int i, j;
//将字符保存进结构体中
for(i = 0; i < 62; i++){
if(i < 10)
List_char[i].c = '0' + i;
else if(i < 36)
List_char[i].c = 'A' + i – 10;
else
List_char[i].c = 'a' + i – 36;
}
scanf("%d",&T);
while(T–&&scanf("%d",&n)){
flog = 0; //初始化为0
memset(Hash,0,sizeof(Hash));
for(i = 0; i < 62; i++)
List_char[i].x = mod_pow((int)List_char[i].c,n); //将字符转化为密文存入结构体中
qsort(List_char,62,sizeof(List_char[0]),cmp);
for(i = 0; !flog && i < 62; i++) //如果不存在多解,这建立哈希表
Hash[List_char[i].x] = i + 1;
getchar();
scanf("%s",str);
len = strlen(str);
for( i = 0, j = 0; j < len/3 && i + 2 < len; i+=3, j++ )
ASC[j] = (str[i] – '0')*100 + (str[i+1] – '0')*10 + str[i+2] – '0';
for( i = 0, j = 0; i < len/3; i++ ){
if(Hash[ASC[i]])
Outstr[j++] = List_char[Hash[ASC[i]] – 1].c;
else
flog = 1; //密文有误
}
if(flog) printf("No Solution
");
else{
for(i = 0; i < j; i++)
printf("%c",Outstr[i]);
printf("
");
}
}
return 0;
}

(如有毛病,欢迎指正,转载请注明出处)
 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » SDUTOJ2165 Crack Mathmen(模拟,哈希表,快速幂)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡