POJ1051 P,MTHBGWB-白红宇

POJ1051 P,MTHBGWB

阅读量：4679 次

发布时间：2019-06-09

本文共 3803 字，大约阅读时间需要 12 分钟。

题目来源：

题目大意：

　　Morse密码里每个字母用长度不定的点和线来表示，一条信息中字母的编码之间用空隙隔开。下表为Morse密码的编码表：

A	.-	H	....	O	---	V	...-
B	-...	I	..	P	.--.	W	.--
C	-.-.	J	.---	Q	--.-	X	-..-
D	-..	K	-.-	R	.-.	Y	-.--
E	.	L	.-..	S	...	Z	--..
F	..-.	M	--	T	-
G	--.	N	-.	U	..-

在上面的基础上，我们加上下面几个编码（它们不属于实际的Morse编码）：

下划线'_' :　　..--　　　　句号'.' :　　---.

逗号',' : .-.-　　　　问号'?' :　 ----

于是信息"ACM_GREATER_NY_REGION"被编码为：

.- -.-. -- ..-- --. .-. . .- - . .-. ..-- -. -.-- ..-- .-. . --. .. --- -.

M.E. Ohaver 提出了一种基于以上Morse编码的加解密方式。标准的Morse码需要字母之间需要间隔，因为Morse码是可变长编码，而且不是prefix-free(这个词不知道怎么翻译，学过编译原理或者知道哈弗曼编码的都可以意会吧=。=)的。所以没有间隔的话会产生歧义，比如".--.-.--",如果不知道在哪里停顿，那么这条信息有可能为"ACM"、"ANK"以及别的一些词。但是，如果我们在编码中加入长度信息，即显式地指明每个字符的编码占几位，如".--.-.--242",就不会有歧义了。

Ohaver的加解密方式如下：

1. 把文本转换为Morse码，去掉Morse码中的空格，加上数字串表示每个字符所占的长度。

2. 把数字串翻转。

3. 再把翻转数字后的编码转换为文本。

加密和解密的方法一样。

比如"AKADTOF_IBOETATUK_IJN"先转为：

".--.-.--..----..-...--..-...---.-.--..--.-..--...----.232313442431121334242"，

将数字翻转后为：

".--.-.--..----..-...--..-...---.-.--..--.-..--...----.242433121136266313232"。

最后再转为文本"ACM_GREATER_NY_REGION".

本题要求实现Ohaver的编码算法。

输入：一组由该算法编码的信息。第一行为整数n表示有多少个待转换的字符串。接下来的n行每行一个字符串，仅有26个大写字母，下划线，句号，逗号和问号组成。每条信息长度不超过100.

输出：对于每个输入，输出其编号和编码后的信息。

Sample Input

5AKADTOF_IBOETATUK_IJNPUELQEWOISE.EIVCAEFNRXTBELYTGD.?EJHUT.TSMYGW?EJHOTDSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E

Sample Output

1: ACM_GREATER_NY_REGION2: PERL3: QUOTH_THE_RAVEN,_NEVERMORE.4: TO_BE_OR_NOT_TO_BE?5: THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG

水题，看懂题目就没太大问题了。

1 // 2 //        POJ1051 P,MTHBGWB 3 //        Memory: 292K        Time: 0MS 4 //        Language: C++        Result: Accepted 5 // 6  7 #include 
      
        8 #include 
       
         9 #include 
        10 11 using namespace std;12 13 map
         
           dictionary;14 15 int main(void) {16     int n;17     cin >> n;18     dictionary['A'] = ".-";19     dictionary['B'] = "-...";20     dictionary['C'] = "-.-.";21     dictionary['D'] = "-..";22     dictionary['E'] = ".";23     dictionary['F'] = "..-.";24     dictionary['G'] = "--.";25     dictionary['H'] = "....";26     dictionary['I'] = "..";27     dictionary['J'] = ".---";28     dictionary['K'] = "-.-";29     dictionary['L'] = ".-..";30     dictionary['M'] = "--";31     dictionary['N'] = "-.";32     dictionary['O'] = "---";33     dictionary['P'] = ".--.";34     dictionary['Q'] = "--.-";35     dictionary['R'] = ".-.";36     dictionary['S'] = "...";37     dictionary['T'] = "-";38     dictionary['U'] = "..-";39     dictionary['V'] = "...-";40     dictionary['W'] = ".--";41     dictionary['X'] = "-..-";42     dictionary['Y'] = "-.--";43     dictionary['Z'] = "--..";44     dictionary['_'] = "..--";45     dictionary['.'] = "---.";46     dictionary[','] = ".-.-";47     dictionary['?'] = "----";48     49     for (int case_id = 1; case_id <= n; ++case_id) {50         int len[100];51         int size;52         string en_message;53         string en_code;54         string de_message;55         cin >> en_message;56         size = en_message.size();57         for (size_t i = 0; i < size; ++i) {58             string code = dictionary[en_message[i]];59             en_code += code;60             len[i] = code.size();61         }62         int p = 0;63         for (int i = size - 1; i >= 0; --i) {64             char code;65             for (map
          
           ::iterator it = dictionary.begin(); it != dictionary.end(); ++it) {66                 if (it->second == en_code.substr(p, len[i])) {67                     code = it->first;68                     break;69                 }70             }71             de_message += code;72             p += len[i];73         }74         cout << case_id << ": " << de_message << endl;75     }76     system("pause");77     return 0;78 }

View Code

转载于:https://www.cnblogs.com/dengeven/p/3255367.html

你可能感兴趣的文章