信息学集训队作业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。该加密方法十分不保险，因为在得到了密文以后，即使没有对应关系表，也能根据英语中可能有的词汇猜出原文。编程完成这项工作。【输入】文件 dict.txt 第一行为一个整数 D(1=d=50000)，为可能出现的单词数目。以下 D行每行

11、一个单词，每个单词最多 20 个字符，所有单词长度和不大于 350,000。文件 puzzle.in 第一行为密文的单词数目T，以下 T 行，每行一个单词。【输出】如果对应表不唯一（忽略原文没有出现的字母）或者无解，输出-1，否则为一个长度为 26 的字符串，即对应表。原文中没有出现的字母处打“*”。【样例】 dict.txt 14BECHANGEIN IS MUSTSLE SEE THE THIS TO WISH WORLD YOU4以下数据都采用上面的 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三、初步情况搜索搜索只知道搜我也认为是搜索。这道题目目前我只能尝试用搜索，但是速度不理想根据数据靠英语单词来猜测？只能搜索，先搜长单词应该更有效。璟我觉得是搜索。剪枝可以借鉴程复杂度就会很高。字符的某些。但是优化的措施一多，应用起来编因为题目所给的数据都很小（即每个 Puzzle.in）而且

13、本文中也出现了如果出现多解打出-1,所以应该只有用搜索来解决。每次选择对应情况数最少的单词来搜吧！效率应该还可以。昆我觉得每次搜索可能对应的单词数最少的密文，这样速度可能比较快似乎只能通过统计字母出现的频率来使搜索简化，当然还需要对不同长度单词的统计。但我依然觉得为了要判断唯一性，似乎还是需要全部搜索可以先判断出每个密文中的单词对应单词表中的单词的所有可能情况，按照可能情况数递增的顺序逐一考虑密文中的每个单词。搜索。不过既然给了一个单词表，可以统计其中字母出现频率，按这个频率搜索对应字母应该很容易找到一组解。如果找不到，无解就很容易判断了；如果找到了，继续找找，就知道是确定解还是许多解的情况了。感觉就是一种搜索。找出最短的一个密文单词，枚举所有的可能单词。然后，用枚举出来的对应关系，将其它单词的一些字母试着，然后再继续枚举未字母最少的密文单词。如此递归，直至找到一个能够所有密文的方法。这道题可以动手编一下，的算法如下：开始的时候，就每个单词扫描数据文件一遍，从单词长度和单词内字母的重复情况方面进行筛选，做成 T 个集合。然后从这 T 个集合中选取F=该集合的基数*（M+1-该单词中出现的字母数量）*(S+1-该单词的字母在其他未选择单词中出现的次数)的积最小的