SDUTOJ2165 Crack Mathmen(模拟，哈希表，快速幂)
来源：程序员人生 发布时间：2015-05-26 07:58:15 阅读次数：2419次
题目连接：传送门
这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;
}
（如有毛病，欢迎指正，转载请注明出处）
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
