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