题目描述明文消息由大写字母 A‑Z 组成加密过程使用一个字母表密钥LLL一个有序字母集合视为循环和一个数值密钥NNN1≤N≤251 \le N \le 251≤N≤25。每个单词独立加密单词间空格保留。加密规则如下规则1\texttt{1}1. 每个单词从左到右逐字母加密。规则2\texttt{2}2. 若明文字母ppp不属于LLL则加密为单个密文字母cciph(p)c \textit{ciph}(p)cciph(p)其中ciph\textit{ciph}ciph将字母在字母表中向前移动NNN位循环。规则3\texttt{3}3. 若明文字母ppp属于LLL则加密为三个字母LLL的第mmm个字母mmm从111开始计数每应用一次规则3\texttt{3}3后mmm递增111并循环后跟ciph(p)\textit{ciph}(p)ciph(p)再后跟LLL的第m1m1m1个字母。给定字母表密钥LLL、数值密钥NNN以及若干密文消息可能含空格要求解密或报告错误。输入保证密钥不会导致解密歧义。输入格式第一行为一个正整数表示测试用例个数随后有一个空行。每个测试用例第一行为字母表密钥LLL第二行为数值密钥NNN第三行为消息条数MMM接下来MMM行每行为一条密文消息可能含空格。各测试用例之间用一个空行分隔。输出格式对于每个测试用例按输入顺序输出每条消息的解密结果每行一条。若无法解密则输出error in encryption。不同测试用例输出之间用一个空行分隔。样例输入1 RSAEIO 2 5 RTSSKAEAGE GRSCAV RGSSCAV RUSIQO RUSSGAACEV JEGIITOOGR样例输出RICE error in encryption EAT error in encryption SEAT HERE题目分析解密过程是加密的逆过程。密文由空格分隔成单词每个单词独立解密。对于每个密文字母或三元组需根据规则2\texttt{2}2和3\texttt{3}3还原明文字母。规则3\texttt{3}3的三元组形式为x c y其中x和y是密钥LLL中相邻的两个字母循环c是ciph(p)\textit{ciph}(p)ciph(p)且x对应于当前的mmm位置y对应m1m1m1位置。解密时若遇到一个密文字母ccc且其ciph−1(c)\textit{ciph}^{-1}(c)ciph−1(c)不属于LLL则按规则2\texttt{2}2处理单字母。否则必须尝试三元组匹配并更新mmm。由于每个单词解密时mmm初始为111且规则3\texttt{3}3的三元组可能跨单词边界题目说明每个单词单独加密空格保留因此空格是分隔符解密时遇到空格则直接保留且mmm值在空格处保持不变从样例看HERE解密为HERE但空格未出现在输出中输入中似乎没有空格。实际上输入消息可能包含空格但样例未显示。根据规则空格保留因此解密时也应保留。算法采用深度优先搜索因为可能存在歧义但题目保证唯一。从密文开头开始逐字符解析尝试两种可能若当前字符能匹配规则2\texttt{2}2的单字母解密则选择该分支若当前及后两个字符能匹配规则3\texttt{3}3则选择三元组分支。因为题目保证唯一解搜索到结束即可输出。解题思路使用递归函数dfs(u,m,n)\texttt{dfs}(u, m, n)dfs(u,m,n)参数uuu当前处理的密文位置下标。mmm当前密钥LLL的索引000基对应规则中的mmm初始为000。nnn已解出的明文字符数用于存储。若uuu到达密文末尾则输出已解出的明文并标记成功。若当前位置是空格则直接输出空格并继续。否则尝试两种可能单字母规则规则2\texttt{2}2当前密文字母cmsg[u]c \textit{msg}[u]cmsg[u]计算pciph−1(c)(c−N mod 26)p \textit{ciph}^{-1}(c) (c - N \bmod 26)pciph−1(c)(c−Nmod26)。若ppp不是密钥字母即ppp不在LLL中则ppp是明文字母记录并递归u1u1u1。三元组规则规则3\texttt{3}3若u2lenu2 \text{len}u2len取三元组x msg[u],c msg[u1],y msg[u2]。检查是否满足x L[m]且y L[(m1) mod len(L)]。若满足则明文字母pciph−1(c)p \textit{ciph}^{-1}(c)pciph−1(c)且ppp必须是密钥字母因为规则3\texttt{3}3只用于密钥字母递归u3u3u3更新m(m1) mod len(L)m (m1) \bmod \text{len}(L)m(m1)modlen(L)。由于每个分支都可能产生结果但题目保证唯一因此第一个找到的解即为答案。若搜索完所有可能无结果则输出错误。注意处理空格时mmm保持不变因为空格不是字母不触发规则3\texttt{3}3的计数递增。单词边界不影响mmm的连续性规则中说明“For each plaintext message the initial value for m is one”即整个消息可能多个单词共用同一个mmm序列空格不改变mmm。因此解密时连续处理整个消息空格仅被保留且mmm不变。代码实现// Deciphering Messages// UVa ID: 828// Verdict: Accepted// Submission Date: 2018-11-07// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string key,msg;intflag,N,keyLength,isKeyLetter[26];charplaintext[102400];voiddfs(intu,intm,intn){if(flag||umsg.length())return;if(umsg.length()){for(inti0;in;i)coutplaintext[i];cout\n;flag1;return;}if(msg[u] ){plaintext[n] ;dfs(u1,m,n1);}else{if(u2msg.length()msg[u1]! msg[u2]! ){intx(msg[u1]-A-N26)%26;if(isKeyLetter[x]msg[u]key[m]msg[u2]key[(m1)%key.length()]){plaintext[n]Ax;dfs(u3,(m1)%key.length(),n1);}}inty(msg[u]-A-N26)%26;if(!isKeyLetter[y]){plaintext[n]Ay;dfs(u1,m,n1);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases,M;cincases;for(intcs0;cscases;cs){if(cs)cout\n;cinkeyNM;memset(isKeyLetter,0,sizeof(isKeyLetter));for(autoletter:key)isKeyLetter[letter-A]1;cin.ignore(256,\n);for(inti1;iM;i){getline(cin,msg);flag0;dfs(0,0,0);if(!flag)couterror in encryption\n;}}return0;}总结本题通过深度优先搜索模拟解密过程利用题目保证的唯一性避免了复杂的状态管理。关键在于正确识别规则2\texttt{2}2和3\texttt{3}3的适用条件并准确处理mmm的循环更新。由于密文可能包含空格空格作为普通字符处理且不影响mmm。算法复杂度为O(2密文长度)O(2^{\text{密文长度}})O(2密文长度)但由于唯一解和提前终止实际运行极快。该解法充分体现了递归回溯在语言解析问题中的应用。