信息學(xué)集訓(xùn)隊(duì)作業(yè)0064-puzzleout

1、題目 0064 Puzzleout（）題目來(lái)源：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#.二、中文翻譯有一個(gè)加密方法是把每個(gè)英文字母映變換成不同的英文字母，給出 26 個(gè)字母的一個(gè)排列 C1,C2,C3，則把加密的時(shí)候應(yīng)該把字母表中第 I 個(gè)字母變換成字母 Ci，空格不變。例如對(duì)于排列 ZYXWVUTSRQPONMLKJIHGFEDCBA，文本 THIS IS THESLE將變成 GSRH RH GSV URIHG HZNKOV。該加密方法十分不保險(xiǎn)，因?yàn)樵诘玫搅嗣芪囊院?，即使沒有對(duì)應(yīng)關(guān)系表，也能根據(jù)英語(yǔ)中可能有的詞匯猜出原文。編程完成這項(xiàng)工作。【輸入】文件 dict.txt 第一行為一個(gè)整數(shù) D(1=d=50000)，為可能出現(xiàn)的單詞數(shù)目。以下 D行每行

11、一個(gè)單詞，每個(gè)單詞最多 20 個(gè)字符，所有單詞長(zhǎng)度和不大于 350,000。文件 puzzle.in 第一行為密文的單詞數(shù)目T，以下 T 行，每行一個(gè)單詞?！据敵觥咳绻麑?duì)應(yīng)表不唯一（忽略原文沒有出現(xiàn)的字母）或者無(wú)解，輸出-1，否則為一個(gè)長(zhǎng)度為 26 的字符串，即對(duì)應(yīng)表。原文中沒有出現(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三、初步情況搜索搜索只知道搜我也認(rèn)為是搜索。這道題目目前我只能嘗試用搜索，但是速度不理想根據(jù)數(shù)據(jù)靠英語(yǔ)單詞來(lái)猜測(cè)？只能搜索，先搜長(zhǎng)單詞應(yīng)該更有效。璟我覺得是搜索。剪枝可以借鑒程復(fù)雜度就會(huì)很高。字符的某些。但是優(yōu)化的措施一多，應(yīng)用起來(lái)編因?yàn)轭}目所給的數(shù)據(jù)都很?。疵總€(gè) Puzzle.in）而且

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