SDUTOJ2165 Crack Mathmen(模擬，哈希表，快速冪)
來源：程序員人生 發布時間：2015-05-26 07:58:15 閱讀次數：2569次
題目連接：傳送門
這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;
}
（如有毛病，歡迎指正，轉載請注明出處）
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
