背景

小K是一位蔚藍教主的崇拜者(Orz教主er)，有一天，他收到了一封匿名信，信告訴了小K由于他表現出色，得到了一次當面Orz教主的機會，但是要當面Orz教主可不那么容易，不是每個人都有資格Orz教主的。所以要破解下面一段密文才可以得到相關的信息，信中有提供加密的規則，但是小K覺得這個問題看似復雜，所以想請你幫忙。

描述

一個長度為n的由小寫字母組成的字符串s1?s2???sn按如下方式加密成3種形式：

1、將字符串翻轉，即對于每一個1≤i≤n來說，si與sn?i+1對換。

2、將字符串中每個字母變為其之后第k個字母，定義z之后的字母為a，其中0≤k≤6且為未知數。

3、將字符串中每個字母變為其之前第k個字母，定義a之前的字母為z，k同2所述。

例如字符串abcd按上面3種方式加密后，在k=1的情況下會依次變為：

1、dcba；
2、bcde；
3、zabc。

現給出信中按以上3種形式分別加密后的3個字符串（不一定按上述例子的順序），要求還原原來的字符串，并輸出告訴小K。

格式

輸入格式

輸入的第1行為一個整數n，表示這個字符串的長度。

下面3行每行1個長度為n的字符串，且保證符合題目要求。

輸出格式

輸出僅包括1行，為還原后的字符串。

樣例1

樣例輸入1

4 zabc dcba bcde

樣例輸出1

abcd

限制

對于10%的數據，輸入給出加密字符串的順序同題目中1、2、3的順序。

對于20%的數據，n≤5；
對于40%的數據，n≤10；
對于60%的數據，n≤255；
對于100%的數據，n≤10000。

時限1s

問題鏈接：Vijos P1449 字符串還原

問題分析：

這個問題是一個單密碼計算問題，也是字符處理問題。

這個問題用窮舉法來解決。輸入的三個字符串都有可能是被翻轉的字符串，假定某個字符串是被翻轉的，那么求得原字符串。

左移和右移是對稱的，右移k位相當于對原先被左移k位字符串的還原，左移k位相當于對原先被右移k位字符串的還原。這個還原也需要窮盡試探，即k=0-6都需要試一下。

另外一種方法用過之后，就不能再用了，程序中需要控制。

程序說明：

程序中，計算后原字符串存放在數組t[]中。

字符串的移位計算是借助數組a[]來實現的，小寫字母的循環移位是通過下標模除計算來實現的。

找到一個解，程序就輸出結果并且結束。

函數shift()實現字符串移位后與原字符串的比較。這時只要有一個字符不匹配則還原的字符串與原字符串不匹配。

題記：

字符處理是計算機程序的永恒話題。

參考鏈接：（略）

AC的C++程序如下：

#include <iostream> #include <string>using namespace std;const int N = 3; const int N2 = 6; const int N3 = 10000; const int N26 = 26;char t[N3+1];char a[] = "abcdefghijklmnopqrstuvwxyz";int shift(char t[], string& s, int n, int k) {for(int i=0; i<n; i++)if(a[(s[i] - 'a' + k + N26) % N26] != t[i])return 0;return 1; }int main() {int n;string s[N];cin >> n >> s[0] >> s[1] >> s[2];// 對輸入的3個字符串分別進行串反轉試探for(int i=0; i<N; i++) {// 串反轉for(int j=0; j<n; j++)t[j] = s[i][n - 1 - j];t[n] = '\0';// 試探右移k個字母for(int j=0; j<N; j++) {if(j != i) {for(int k=0; k<=N2; k++)if(shift(t, s[j], n, k)) {// 試探左移k個字母for(int l=0; l<N; l++) {if(l != i && l != j)if(shift(t, s[l], n, -k)) {cout << t << endl;return 0;}}}}}}return 0; }

轉載于:https://www.cnblogs.com/tigerisland/p/7563822.html

總結

以上是生活随笔為你收集整理的Vijos P1449 字符串还原【密码】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。