信息學集訓隊作業(yè)0064-puzzleout

1、題目 0064 Puzzleout（）題目來源：Tehran01者：林希德一、英文原文Puzzle OutThe scientific committee members of the 26CM/ICPC, who design the contest problems,use the following encryption algorithm to communicate the problem drafts securely through theernet. To encrypext, all occurrenof each letter is replaced winother le

2、tter (siblyitself), sucht no two letters are encrypted to the same letter. Both original and encrypted textsconsist of only upper-case letters and bls. Bls are not encrypted and are repeated exactly inthe encrypted text. As an exle, the string GSRH RH GSV URIHG HZNKOV is the encrypted formLE accordi

3、ng to the encryption table (A Z, B Y, C X, ,of THIS IS THEZ A).SA recipient of a problem drafs lost the encryption table, but he has a dictionary which includeshe problems. You are to help him set up a decryption table toall thesible words appearingenable him restore the original problem draft from

4、the encrypted one. Given a dictionary of theoriginal words usedhe text, and the encrypted text, we want to find the right encryption tablesucht after decrypting the given encrypted text back to the original one, all words can be foundhe dictionary.Input (filename: E.IN)Thepart of the input file is a

5、 dictionary of English words common to all test cases. Theline of the file is d (1 d 50000); the number of wordshe dictionary, followed by d lineseach containing a wordhe dictionary. The wordshe dictionary are sorted in alphabeticalorder and all are in uppercase. Each word has at most 20 characters,

6、 but you can amet sumof the length of all wordshe dictionary is no moren 350,000. The next line contains a singleeger t (1 t 10), the number of test cases, followed by the input data for each test case. Eachtest case, which is preceded by a single blline, consists of multiple lines in the input file

7、forming the encrypted text. Each line has a string containing only uppercase letters and bl. Youmay amet no line break is occurred in the middle of a word and there may be arbitrarynumber of blcharacters atof each line.um length of input lines is 80.Output (filename: E.OUT)The output file contains e

8、xactly t lines, each corresponding to a test case. Each line should containasinglestringof26characterswhichistheencryptionofthestringABCDEFGHIJKLMNOPQRSTUVWXYZ according to the encryption table used in the test case.Lettershe output string should be in uppercase. It issiblet some letters do not appe

9、ar inthe encrypted texdecrypted verall.his case, put a * mark in place of those letters not appearingheof the input text. If the test case has no solution, the output line should contain#No solution#. If there is moren onesible encryption table for a test case, the outputline should contain #Moren o

10、ne solution#.二、中文翻譯有一個加密方法是把每個英文字母映變換成不同的英文字母，給出 26 個字母的一個排列 C1,C2,C3，則把加密的時候應該把字母表中第 I 個字母變換成字母 Ci，空格不變。例如對于排列 ZYXWVUTSRQPONMLKJIHGFEDCBA，文本 THIS IS THESLE將變成 GSRH RH GSV URIHG HZNKOV。該加密方法十分不保險，因為在得到了密文以后，即使沒有對應關系表，也能根據(jù)英語中可能有的詞匯猜出原文。編程完成這項工作?！据斎搿课募?dict.txt 第一行為一個整數(shù) D(1=d=50000)，為可能出現(xiàn)的單詞數(shù)目。以下 D行每行

11、一個單詞，每個單詞最多 20 個字符，所有單詞長度和不大于 350,000。文件 puzzle.in 第一行為密文的單詞數(shù)目T，以下 T 行，每行一個單詞?！据敵觥咳绻麑聿晃ㄒ唬ê雎栽臎]有出現(xiàn)的字母）或者無解，輸出-1，否則為一個長度為 26 的字符串，即對應表。原文中沒有出現(xiàn)的字母處打“*”。【樣例】 dict.txt 14BECHANGEIN IS MUSTSLE SEE THE THIS TO WISH WORLD YOU4以下數(shù)據(jù)都采用上面的 dict.txt puzzle.in5GSRH RHGSVURIHGHZNKOVPuzzle.outZ*VU*SR*ON*K*IHG*Pu

12、zzle.in 12IZM BMVU SP UGPRGTANP IZM KFVG UZVPP FA UGPKZWCQPuzzle.outTSRQP*NGF*CBAZ*WVUM*K*I*Puzzle.in 2XYZABCDEFGPuzzle.out-1puzzle.in 2XZYABDPuzzle.out-1三、初步情況搜索搜索只知道搜我也認為是搜索。這道題目目前我只能嘗試用搜索，但是速度不理想根據(jù)數(shù)據(jù)靠英語單詞來猜測？只能搜索，先搜長單詞應該更有效。璟我覺得是搜索。剪枝可以借鑒程復雜度就會很高。字符的某些。但是優(yōu)化的措施一多，應用起來編因為題目所給的數(shù)據(jù)都很?。疵總€ Puzzle.in）而且

13、本文中也出現(xiàn)了如果出現(xiàn)多解打出-1,所以應該只有用搜索來解決。每次選擇對應情況數(shù)最少的單詞來搜吧！效率應該還可以。昆我覺得每次搜索可能對應的單詞數(shù)最少的密文，這樣速度可能比較快似乎只能通過統(tǒng)計字母出現(xiàn)的頻率來使搜索簡化，當然還需要對不同長度單詞的統(tǒng)計。但我依然覺得為了要判斷唯一性，似乎還是需要全部搜索可以先判斷出每個密文中的單詞對應單詞表中的單詞的所有可能情況，按照可能情況數(shù)遞增的順序逐一考慮密文中的每個單詞。搜索。不過既然給了一個單詞表，可以統(tǒng)計其中字母出現(xiàn)頻率，按這個頻率搜索對應字母應該很容易找到一組解。如果找不到，無解就很容易判斷了；如果找到了，繼續(xù)找找，就知道是確定解還是許多解的情況了。感覺就是一種搜索。找出最短的一個密文單詞，枚舉所有的可能單詞。然后，用枚舉出來的對應關系，將其它單詞的一些字母試著，然后再繼續(xù)枚舉未字母最少的密文單詞。如此遞歸，直至找到一個能夠所有密文的方法。這道題可以動手編一下，的算法如下：開始的時候，就每個單詞掃描數(shù)據(jù)文件一遍，從單詞長度和單詞內(nèi)字母的重復情況方面進行篩選，做成 T 個集合。然后從這 T 個集合中選取F=該集合的基數(shù)*（M+1-該單詞中出現(xiàn)的字母數(shù)量）*(S+1-該單詞的字母在其他未選擇單詞中出現(xiàn)的次數(shù))的積最小的