题目描述Sandorf\texttt{Sandorf}Sandorf密码使用一个6×66 \times 66×6的硬纸板方框上面有一些孔洞共999个孔。加密过程如下步骤1\texttt{1}1. 将明文消息末尾补充#字符直到长度为363636的倍数然后将整个字符串反转。步骤2\texttt{2}2. 将密码框放在纸上定位标记朝上。步骤3\texttt{3}3. 从反转后的消息中依次取999个字符按密码框上的孔洞位置从左到右、从上到下填入6×66 \times 66×6矩阵。步骤4\texttt{4}4. 将密码框顺时针旋转90∘90^\circ90∘重复步骤3\texttt{3}3直到密码框回到初始方向旋转444次。每次旋转填入999个字符共444次填满363636个格子得到一个编码组。步骤5\texttt{5}5. 重复步骤2\texttt{2}2到4\texttt{4}4直到所有字符被处理。最后按行连接所有编码组得到密文。给定密文要求解密恢复原始明文。密文每行长度不定总长度不超过108108108个字符即最多333个编码组。输入格式输入包含若干行每行一个密文字符串可能为空行。密文由可打印字符组成长度不超过108108108。输入以文件结束终止。输出格式对于每行密文输出解密后的明文。每个明文占一行移除末尾填充的#字符。不同明文之间无额外空行。样例输入irdetn ihtoteao pesms soiaCet snaoi #e#r# edt#aasdrttln ca reyor feneiv o#kginasksoaemlt f odatrnip as ene w#lerhiomfte t rSp se ntt.is id,raal o#r#i#etbanagvareioml nbfooheo lny e# s#holp#lpt#iiok# w#so ts.tiis h H### ##d#l##a###n#o)D##g##n#o#样例输出Competition is a disease that sooner or later infects every trade and profession and makes it take a long step forward. Still, it remains the obligation of every honorable man to oppose it with his skills. Donald Honig)题目分析解密是加密的逆过程。密文按363636个字符为一组编码组分组每组对应一个6×66 \times 66×6矩阵。加密时矩阵的363636个格子被分444轮填入每轮999个孔位。解密时需要还原每个矩阵中字符的填入顺序即得到字符在矩阵中的位置与密文子串中字符的映射关系。由于加密时每次旋转90∘90^\circ90∘孔位位置也随之旋转。给定初始孔位映射表可以提前计算出密文子串中第kkk个字符对应矩阵中的哪个位置即其在最终按行排列的矩阵中的索引。有了这个映射即可从密文子串恢复出363636个字符的矩阵然后按行连接再反转整个组最后移除末尾#。解题思路预计算映射表mapping[36]\textit{mapping}[36]mapping[36]其中mapping[i]\textit{mapping}[i]mapping[i]表示密文子串中第iii个字符000基在解码后6×66 \times 66×6矩阵按行展开时的位置索引000到353535。例如初始孔位位置为[1,3,5,10,14,19,22,29,33]按行展开索引旋转90∘90^\circ90∘、180∘180^\circ180∘、270∘270^\circ270∘后的孔位位置分别为对应的旋转坐标。将这些位置按顺序第000轮、第111轮、第222轮、第333轮填入mapping\textit{mapping}mapping使得mapping[i]\textit{mapping}[i]mapping[i]为第iii个密文字符应放在矩阵的哪个位置。对于每个密文组encrypted\textit{encrypted}encrypted长度为363636初始化一个长度为363636的字符串square\textit{square}square全空格。遍历iii从000到353535将encrypted[i]\textit{encrypted}[i]encrypted[i]放入square[mapping[i]]\textit{square}[\textit{mapping}[i]]square[mapping[i]]。然后对square\textit{square}square反转因为加密时先反转消息解密时需反转回来再将其插入到明文的前面因为加密时按组顺序生成解密时需按组逆序还原。最后移除末尾的#字符。由于密文可能跨多行题目要求每行单独解密但样例中第一行包含完整密文第二行是另一段密文。实际处理中按行读取并逐行解密即可。代码实现// Sandorfs Cipher// UVa ID: 795// Verdict: Accepted// Submission Date: 2018-03-21// UVa Run Time: 0.010s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmapping[36]{1,3,5,10,14,19,22,29,33,8,11,15,18,23,26,28,31,35,2,6,13,16,21,25,30,32,34,0,4,7,9,12,17,20,24,27};stringdecode(string encrypted){string message;for(inti0;iencrypted.length();i36){string squareencrypted.substr(i,36);string decrypted;for(inti0;i36;i)decryptedsquare[mapping[i]];reverse(decrypted.begin(),decrypted.end());message.insert(0,decrypted);}while(message.back()#)message.pop_back();returnmessage;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;string line;while(getline(cin,line)){if(cases0)cout\n;coutdecode(line)\n;while(getline(cin,line),line.length()0)coutdecode(line)\n;}return0;}总结本题通过预计算孔位旋转映射将复杂的矩阵旋转和字符填充转换为简单的索引映射使解密过程变为直接的字符串置换和反转。关键点在于正确计算映射表确保密文子串中的每个字符被放置在矩阵的正确位置。解密时按组处理每组先还原矩阵再反转最后连接并移除填充字符。该解法时间复杂度O(L)O(L)O(L)空间O(1)O(1)O(1)适用于长度不超过108108108的密文。预计算映射表体现了将几何变换转化为数据映射的通用技巧。