UVa 468 Key to Success

题目描述题目要求根据频率分析解码一段密文。已知明文字符串和密文字符串来自同一个人且该人使用字母的相对频率在不同文本中保持一致。因此明文中出现频率最高的字母对应于密文中出现频率最高的字母第二高频的对应于第二高频的依此类推。区分大小写。需要输出解码后的密文。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例包含两行第一行为明文未编码的文本第二行为密文编码后的文本。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出一行解码后的密文。两个连续测试用例的输出之间由一个空行分隔。样例输入1 abacxbacac qqqqqrrrssstt输出aaaaacccccbbxx题目分析本题的核心是根据字母频率统计进行映射然后解码。频率统计统计明文中每个字母包括大小写出现的次数。统计密文中每个字母出现的次数。分别按频率降序排序得到两个有序列表。映射建立由于频率最高的字母相互对应第二高的相互对应依此类推可以建立从密文字母到明文字母的映射。如果密文中的字母数量少于明文中的字母数量即某些明文字母未在密文出现则这些字母不需要映射。解码遍历密文字符串中的每个字符如果是字母则替换为映射后的字母。否则非字母字符保持不变。特殊情况明文中可能出现密文中没有的字母这些字母在解码时不会出现。如果多个字母出现频率相同题目假设“没有两个字母使用频率相同”因此排序结果唯一。复杂度分析统计频率O(L)O(L)O(L)排序O(26log⁡26)O(26 \log 26)O(26log26)完全可接受。代码实现// Key to Success// UVa ID: 468// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{charletter;intfrequency;booloperator(constitemanother)const{if(frequency!another.frequency)returnfrequencyanother.frequency;elsereturnletteranother.letter;}};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);for(inti1;icases;i){if(i1)cout\n;getline(cin,line);string plain_line,encoded_line;mapchar,intplain,encoded;getline(cin,plain_line);for(intj0;jplain_line.length();j)if(isalpha(plain_line[j]))plain[plain_line[j]];getline(cin,encoded_line);for(intj0;jencoded_line.length();j)if(isalpha(encoded_line[j]))encoded[encoded_line[j]];vectoritemtext1,text2;for(autop:plain)text1.push_back((item){p.first,p.second});for(autop:encoded)text2.push_back((item){p.first,p.second});sort(text1.begin(),text1.end());sort(text2.begin(),text2.end());mapchar,charcode;for(intj0;jtext1.size();j)code[text2[j].letter]text1[j].letter;for(autoc:encoded_line)if(isalpha(c))coutcode[c];elsecoutc;cout\n;}return0;}