算法分析与设计(五)

http://192.168.173.163/JudgeOnline/contest.php?cid=1255

密码:123654

算法实验5(密码学)

凯撒加密

题目描述

凯撒加密法,或称恺撒加密、恺撒变换、变换加密,是一种最简单且最广为人知的加密技术。它是一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。
例如,当偏移量是左移3的时候:
明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表:DEFGHIJKLMNOPQRSTUVWXYZABC
使用时,加密者查找明文字母表中需要加密的消息中的每一个字母所在位置,并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作,得到原来的明文。例如:
明文:THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文:WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
现在给定你一个字符串S(长度不会超过1000000)和一个整数k(-1000000000<=k<=1000000000),分别代表接受者收到的密文和在加密该密文时向后的偏移量,你的任务是计算出原来的明文
注意:只有字母在加密时才会发生偏移,其它字符保持不变

输入

输入包含多组数据,其中第一行为数据组数T(T<=10)

每组数据第一行为一个字符串S,由数字、字母以及常见字符组成(不含空格),第二行为一个整数k代表加密时向后的偏移量(|S|<=1000000,-1000000000<=k<=1000000000)

输出

对每组数据,输出一行字符串,代表输入中的密文对应的明文。

样例输入

1
2
3
1
DEFGHIJKLMNOPQRSTUVWXYZABC
3

样例输出

1
ABCDEFGHIJKLMNOPQRSTUVWXYZ

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
string s;
long long k;
cin >> s;
cin >> k;
k = k % 26;
for (int i = 0; i < s.length(); i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
int r = (int(s[i]) - 65) % 26;
int pos = ((r - k) % 26 + 26) % 26;
cout << char(pos + 65);
}
else if(s[i] >= 'a' && s[i] <= 'z'){
int r = (int(s[i]) - 97) % 26;
int pos = ((r - k) % 26 + 26) % 26;
cout << char(pos + 97);
}
else {
cout << s[i];
}
}
cout << endl;
}
return 0;
}

维吉尼亚密码

题目描述

Vigenère 加密在操作时需要注意:

忽略参与运算的字母的大小写,并保持字母在明文 M中的大小写形式;

当明文M的长度大于密钥k的长度时,将密钥k重复使用。 例如,明文 M=Helloworld,密钥 k=abc时,密文 C=Hfnlpyosnd。

输入

第一行为一个字符串,表示密钥k,长度不超过 100,其中仅包含大小写字母。

第二行为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。

输出

输出共1行,一个字符串,表示输入密钥和密文所对应的明文。

样例输入

1
2
CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

样例输出

1
Wherethereisawillthereisaway

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main() {
int k[1001];
int c[1001];
int m[1001];
memset(c, -1, sizeof(c));
string tk;
string tc;
cin >> tk >> tc;
for (int i = 0; i < tk.length(); i++) {
k[i] = int(tolower(tk[i]))-97;
}
for (int i = 0; i < tc.length(); i++) {
c[i] = int(tolower(tc[i]))-97;
}
int p = -1;
for (int i = 0; i < tc.length();i++) {
p++;
p = p % tk.length();
m[i] = (((c[i] - k[p]) % 26 + 26) % 26) + 97;
}
for (int i = 0; i < tc.length(); i++) {
if (tc[i] < 'a')
cout << char(m[i] - 32);
else
cout << char(m[i]);
}
cout << endl;
return 0;
}

简单的密码

题目描述

密码是按特定法则编成,用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段,将其变为除通信双方以外其他人所不能读懂的信息编码,这种独特的信息编码就是密码。
现在我们定义一种非常简单的密码,它的长度固定为n(n<=30)并且每一位只能由数字0或者数字1组成,但是有一个特殊的要求:一个密码序列中至少要有连续的3个0出现才可以,否则就是无效的。现在给定你密码序列的长度n,你的任务是计算长度为n的序列能产生多少种不同的并且有效的密码?

输入

输入包含多组数据,每组数据只有一个正整数n(1<=n<=30)代表密码序列的长度,单独占一行。

输出

对每组数据,输出一个整数,代表长度为n的序列能产生的不同密码的种类数。

样例输入

1
2
3
4
5
6

样例输出

1
2
3
3
8
20

AC代码

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
int k[32] = { 0,0,0,1,3,8,20,47,107,238,520,1121,2391,5056,10616,22159,46023,95182,196132,402873,825259,1686408,3438828,6999071,14221459,28853662,58462800,118315137,239186031,483072832,974791728 };
int main(){
int n;
while (cin>>n)
cout<<k[n]<<endl;
return 0;
}

有趣的素数

题目描述

素数被广泛地应用于密码学中,所谓的公钥就是将想要传递的信息在编码时加入砠数,编码之后传给收信人,任何人收到此信息之后,若没有此收信人所拥有的秘钥,则在解密的过程中将会因为分解质因数过久而无法破解信息,可见素数在密码学中的重要性。
现在给你n(2<=n<=16)个正整数1,2,3…n,你的任务是把这n个正整数组成一个环,使得任意相邻的两个整数之和为一个素数,输出有多少种合法方案。

输入

多组输入数据,每组数据只有一个正整数n(2<=n<=16)代表有n个正整数 1,2,3…n

输出

对每组数据,输出一个整数,代表有多少种不同的可行方案数。

样例输入

1
2
6
8

样例输出

1
2
2
4

对于输入样例中的6,有以下2种合法方案(首尾相连构成一个环)
1 4 3 2 5 6

1 6 5 2 3 4

对于输入样例中的8,有以下4种合法方案(首尾相连构成一个环)
1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

int n;
int cnt = 0;
int t[20];
bool f[20];
int sum = 0;

bool judge(int x) {
for (int i = 2; i <= sqrt((double)x); i++) {
if (x % i == 0)
return false;
}
return true;
}


void back(int s[]) {
if (cnt == n)
sum++;
else {
if (cnt == 0)
t[cnt++] = s[0];
for (int i = 1; i < n; i++) {
if (f[i] == false) {
t[cnt++] = s[i];
f[i] = true;
int temp = 0;
int pos = cnt - 1;
if (cnt == n) {
temp = t[pos] + t[pos - 1];
int temp2 = t[pos] + t[0];

if (judge(temp) == true && judge(temp2) == true)
back(s);
}
else {
temp = t[pos] + t[pos - 1];
if (judge(temp) == true)
back(s);
}
cnt--;
f[i] = false;
}
}
}
}

int main() {

while (cin >> n){
sum = 0;
cnt = 0;
memset(t, 0, sizeof(t));
memset(f, false, sizeof(f));
int s[20];
for (int i = 0; i < n; i++)
s[i] = i + 1;
back(s);
cout << sum << endl;
}
return 0;
}

数据加密

题目描述

要求你用下面给定的方法对数据实现加密。给定长度为n的字符串S(1<=n<=2000,S中只有大写字母)作为明文,要求构造一个字符串T作为密文,起初T是一个空串,之后反复执行以下任意操作

1.从S的头部删除一个字符,加入到T的尾部
2.从S的尾部删除一个字符,加入到T的尾部

最后S会变成空串,T会变成一个长度为n的字符串作为密文。当然并非所有的构造方案都是符合条件的,我们要求构造出的密文T的字典序尽可能小,你能找出这个字典序最小的密文吗?

输入

输入包含多组数据,每组数据占两行,第一行为一个整数n(1<=n<=2000)代表字符串S的长度,第二行为一个长度为n的字符串S代表明文,保证S中只有大写字母

输出

对每组数据,输出一行字符串,代表构造出的字典序最小的密文T

样例输入

1
2
6
ACDBCB

样例输出

1
ABCBCD

AC代码

字典序是指从前往后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符更小的字符串更小,如果相同则继续比较第2个字符……如此继续,来比较整个字符串的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
int n;
char a[2002];

int main()
{
while (cin >> n) {
for (int i = 0; i < n; i++)
cin >> a[i];
int l = 0, r = n - 1;
while (l <= r) {
bool flag = false;
for (int i = 0; l + i < n; i++) {
if (a[l + i] < a[r - i]) {
flag = true;
break;
}
else if (a[l + i] > a[r - i])
break;
}
if (flag) cout << a[l++];
else cout << a[r--];
}
cout << endl;
}
return 0;
}
-------------end ♥-------------