本文主要是介绍Vijos P1449 字符串还原【密码】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
背景
小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;
}
这篇关于Vijos P1449 字符串还原【密码】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
