您當(dāng)前位置：首頁 > php開源 > php教程 > SDUTOJ2165 Crack Mathmen(模擬，哈希表，快速冪)

SDUTOJ2165 Crack Mathmen(模擬，哈希表，快速冪)

來源：程序員人生發(fā)布時(shí)間：2015-05-26 07:58:15 閱讀次數(shù)：2578次

題目連接：傳送門

這1題是我們昨天省賽集訓(xùn)的題目，我可給坑慘了。不過所幸沒有給白坑，學(xué)到了1些東西。最有感觸的是這個(gè)

for(int i = 0 ; i < strlen(str); i++) //危險(xiǎn)，切勿模仿

如果數(shù)組大1些，這樣寫就直接超時(shí)。我之前找了好久都沒發(fā)現(xiàn)，最后學(xué)長告知我把他寫成這樣

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

為何呢？緣由是如果數(shù)組較大的話，那末就要計(jì)算 strlen(str)次的str的長度，這樣會(huì)致使超時(shí)。但是如果將其保存在1個(gè)整型變量中，那末就只要計(jì)算1次str的長度就行了。這樣就不會(huì)超時(shí)了。感覺自己瞬間就漲姿式了，之前多是由于數(shù)組比較小，完全沒有注意到這個(gè)，這1次數(shù)組大了1些，我可是吃盡了苦頭。大家切記啊，不然準(zhǔn)備好1晚上的時(shí)間來查錯(cuò)吧。

哈希表聽起來是否是很高大上啊，用了這么久，現(xiàn)在才知道那玩意叫哈希表。不過哈希表的確是個(gè)好東西，他可使你的查找時(shí)間是 O(1) ，為何呢？由于他1次就能夠找到了。我來講說哈希表吧，你1看，你就猛然1驚，怎樣是這玩意。

哈希表（文字版）：

在很多數(shù)據(jù)結(jié)構(gòu)中（線性表，樹等），記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的，和記錄的關(guān)鍵字之間不存在肯定關(guān)系，因此在結(jié)構(gòu)中查找記錄時(shí)，需要進(jìn)行1系列和關(guān)鍵字的比較。這1類查找方法建立在比較的基礎(chǔ)上，所以其查找的效力依賴于比較的次數(shù)。理想情況固然是不經(jīng)任何比較，1次就得出結(jié)果。那就必須在記錄的存儲(chǔ)位置和他的關(guān)鍵字之間建立1個(gè)肯定的對(duì)應(yīng)關(guān)系 f ,使每個(gè)關(guān)鍵字和結(jié)構(gòu)中1個(gè)唯1的貯存位置相對(duì)應(yīng)。因此在查找時(shí)只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系 f 就能夠找到定值 K的像 f (K)。若結(jié)構(gòu)中存在關(guān)鍵字與K相等的記錄，則一定在 f（k）的貯存位置上，所以我們1次就能夠找到記錄。我們稱這個(gè)為哈希函數(shù)。我們?cè)谑褂弥谐３Ｊ褂么虮矸ㄅc之結(jié)合，所以哈希表就誕生了。

哈希表（表達(dá)式版）： f(key1) = key2 （這個(gè)表達(dá)式不是固定，我想說的重點(diǎn)是建立1個(gè)映照關(guān)系，不管你的表達(dá)式是1次函數(shù)，還是2次，3次都行，這個(gè)根據(jù)需要來變化）

――――――――――――――――――――分割線――――――――――――――――――

瞎扯了很多，我們現(xiàn)在來看看題。題目想要你做的就是將1串密文還原。對(duì)本題，由于還有1個(gè) n 次方的問題所以我們又要用到快速冪。不知道快速冪的請(qǐng)移步：這里

這1題我們可以這樣處理，摹擬他的加密方式將，他所用到的字符都進(jìn)行加密，將其全部存起來，然后我們根據(jù)密文1個(gè)個(gè)的比較，比較時(shí)我們就能夠使用哈希表，來提高效力。固然不使用這1題好像也能過，不過時(shí)間上那就......。所以我們還是用1下哈希表，這樣快1些也方便。最后我們?cè)賹㈩}目的細(xì)節(jié)處理1下這1題就完成了。對(duì) No Solution的情況，斟酌1下，第1是將多解的刪去，然后包括不使用的字符（在本題也就是除字母和數(shù)字之外的字符）也刪去。這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]; //用結(jié)構(gòu)體將字符，與其對(duì)應(yīng)的加密后的文本存進(jìn)結(jié)構(gòu)體數(shù)組 char str[MAXN],Outstr[MAXN/3]; //str為輸入文本，Outstr為輸出文本 int ASC[MAXN/3],Hash[997],flog; //ASC存每一個(gè)字母的加密文本，Hash為加密的密文與其數(shù)組下標(biāo)的哈希表 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; //將字符保存進(jìn)結(jié)構(gòu)體中 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); //將字符轉(zhuǎn)化為密文存入結(jié)構(gòu)體中 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; }

（如有毛病，歡迎指正，轉(zhuǎn)載請(qǐng)注明出處）

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生

------分隔線----------------------------

上一篇 自己搭建的個(gè)人自學(xué)的社區(qū)

下一篇 DevExpress 用戶控件分頁（中）

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關(guān)注

欄目熱點(diǎn)

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

SDUTOJ2165 Crack Mathmen(模擬，哈希表，快速冪)

SDUTOJ2165 Crack Mathmen(模擬，哈希表，快速冪)