企业官网建设流程全解析

题目描述

题目要求破解凯撒密码。加密时，将字母A∼Z\texttt{A} \sim \texttt{Z}A∼Z映射为1∼261 \sim 261∼26，空格映射为000，然后加上密钥KKK（模272727）得到密文。解密时，需要尝试所有K=0∼26K = 0 \sim 26K=0∼26，选择使解密后文本中匹配词典中的单词数量最多的KKK。输出解密后的文本，并按要求分行（每行不超过606060字符，单词不能跨行）。

输入格式

首先输入词典，每行一个单词（大写字母，长度≤20\le 20≤20），以#结束。然后输入一行密文（长度≤250\le 250≤250字符）。

输出格式

输出解密后的文本，每行尽量长但不超过606060字符，单词不跨行。

样例

输入

THIS DAWN THAT THE ZORRO OTHER AT THING # BUUBDLA PSSPABUAEBOX

输出

ATTACK ZORRO AT DAWN

题目分析

本题的核心是尝试所有密钥，统计匹配的单词数，选择最优密钥。

解密过程

对于每个KKK（000到262626），将密文字符转换为数字（空格为000，A∼Z\texttt{A} \sim \texttt{Z}A∼Z为1∼261 \sim 261∼26），减去KKK模272727后转回字符。

评分

将解密后的文本按空格分割成单词，统计在词典中出现的单词数量。选择匹配数最大的KKK。

输出格式

将解密后的文本按单词输出，每行不超过606060个字符，单词间用空格分隔。注意行首不能有空格，行尾不能有空格。

复杂度分析

词典大小≤100\le 100≤100，密文长度≤250\le 250≤250，尝试272727个密钥，每次分割单词并查词典，可接受。

代码实现

// Caesar Cypher// UVa ID: 554// Verdict: Accepted// Submission Date: 2017-02-21// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);set<string>dictionary;string word;while(cin>>word,word!="#")dictionary.insert(word);string sentence;cin.ignore(1024,'\n');getline(cin,sentence);intmax_matches=0,K=0;string plain;for(intk=0;k<=26;k++){intmatches=0;string original;for(inti=0;i<sentence.length();i++){intletter=sentence[i]==' '?0:(sentence[i]-64);letter=(letter+27-k)%27;if(letter==0)original+=' ';elseoriginal+=(char)(letter+64);}istringstreamin(original);while(in>>word)if(dictionary.count(word)==1)matches++;if(matches>max_matches){max_matches=matches;K=k;plain=original;}}vector<string>words;stringstreamout(plain);while(out>>word)words.push_back(word);inti=0,j=0;while(i<words.size()){if(j>0){if((j+1+words[i].length())>=60){cout<<'\n';j=0;}else{cout<<' '<<words[i];j+=(1+words[i].length());i++;}}else{cout<<words[i];j+=words[i].length();i++;}}if(j>0)cout<<'\n';return0;}