题目内容

在一个秘密组织中，成员们需要进行加密通信以保护敏感信息不被敌人获得。组织中的技术专家为了确保信息的安全性，研发出了一种新的加密算法。

该算法的原理是，对于待加密的字符串中的每个字母，根据预先定义好的数组 a 中对应的元素，对其进行偏移。其中，数组 a 的前三位已经被设定为 a[0]=1,a[1]=2,a[2]=4，而当 i>=3 时，数组元素 a[i] 的值是 a[i-1]+a[i-2]+a[i-3]。

在组织中，每个成员都知道完整的数组 a，因此可以使用该算法对通信内容进行加密。当成员 A 想要给成员 B 发送一条加密信息时，他会先将消息中的每个字母按照数组 a 中对应的元素进行偏移，从而得到加密后的消息。为了解密该信息，成员 B 需要知道完整的数组 a，并对每个字母根据对应的数组元素进行反向偏移。只有这样，他才能够正确地读取消息内容。

现在小红得到一个未加密的字符串，他想知道加密以后的字符串是啥，但是他不知道数组 a 是啥，请问身为组织成员的你能不能帮帮他？

输入描述

输入一行未加密的字符串，字符串长度不会超过100000。

输出描述

输出加密后的字符串

样例

输入

abcde

输入

bdgkr

题目大意

这道题目要求将一个未加密的字符串通过特定的加密算法转换为加密后的字符串

思路

1.初始化数组 a：

根据字符串长度 n，初始化一个长度为 n 的数组 a。设定前三个元素的值： a[0] = 1 a[1] = 2 a[2] = 4 对于 i >= 3，依次计算 a[i] = a[i-1] + a[i-2] + a[i-3]。

2.加密字符串：

遍历字符串 s 中的每个字符 s[i]：计算加密后的字符 t[i] = s[i] + a[i]。将结果转换为字符，并拼接到加密后的字符串 t 中。 3.输出结果：

输出加密后的字符串 t。

时间复杂度：O(n)，其中 n 是字符串的长度。需要一次遍历来计算数组 a，以及一次遍历来加密字符串。

空间复杂度：O(n)，需要存储数组 a 和加密后的字符串 t。

时间复杂度

$O(n)$

代码

C++代码

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s, t = ""; // s为未加密的字符串，t为加密后的字符串
	cin >> s; // 读取未加密的字符串
	int n = s.length(); // 获取字符串的长度
	int a[n] = {0}; // 定义数组a，用于存储每个位置的偏移量，初始化为0
	
	// 遍历字符串的每个字符，计算偏移量并生成加密后的字符串
	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			a[i] = 1; // a[0] = 1
		} else if (i == 1) {
			a[i] = 2; // a[1] = 2
		} else if (i == 2) {
			a[i] = 4; // a[2] = 4
		} else {
			a[i] = a[i - 1] + a[i - 2] + a[i - 3]; // a[i] = a[i-1] + a[i-2] + a[i-3]
		}
		a[i]%=26;
		// 将当前字符加上对应的偏移量后转换为新的字符，并拼接到加密后的字符串t中
		t += char((s[i]-'a' + a[i])%26+'a');
	}
	
	cout << t << endl; // 输出加密后的字符串
	return 0; // 程序结束
}

python代码

# 导入模块
def encrypt(s):
    t = ""  # s为未加密的字符串，t为加密后的字符串
    n = len(s)  # 获取字符串的长度
    a = [0] * n  # 定义数组a，用于存储每个位置的偏移量，初始化为0

    # 遍历字符串的每个字符，计算偏移量并生成加密后的字符串
    for i in range(n):
        if i == 0:
            a[i] = 1  # a[0] = 1
        elif i == 1:
            a[i] = 2  # a[1] = 2
        elif i == 2:
            a[i] = 4  # a[2] = 4
        else:
            a[i] = a[i - 1] + a[i - 2] + a[i - 3]  # a[i] = a[i-1] + a[i-2] + a[i-3]
        a[i] %= 26
        # 将当前字符加上对应的偏移量后转换为新的字符，并拼接到加密后的字符串t中
        t += chr((ord(s[i]) - ord('a') + a[i]) % 26 + ord('a'))

    return t


# 读取未加密的字符串
s = input()
# 输出加密后的字符串
print(encrypt(s))

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s, t = ""; // s为未加密的字符串，t为加密后的字符串
        s = sc.next(); // 读取未加密的字符串
        int n = s.length(); // 获取字符串的长度
        int[] a = new int[n]; // 定义数组a，用于存储每个位置的偏移量，初始化为0

        // 遍历字符串的每个字符，计算偏移量并生成加密后的字符串
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                a[i] = 1; // a[0] = 1
            } else if (i == 1) {
                a[i] = 2; // a[1] = 2
            } else if (i == 2) {
                a[i] = 4; // a[2] = 4
            } else {
                a[i] = a[i - 1] + a[i - 2] + a[i - 3]; // a[i] = a[i-1] + a[i-2] + a[i-3]
            }
            a[i] %= 26;
            // 将当前字符加上对应的偏移量后转换为新的字符，并拼接到加密后的字符串t中
            t += (char) ((s.charAt(i) - 'a' + a[i]) % 26 + 'a');
        }

        System.out.println(t); // 输出加密后的字符串
    }
}

#P1589. 2022.10.11-秋招-字母加密

2022.10.11-秋招-字母加密

题目内容

输入描述

输出描述

样例

题目大意

思路

时间复杂度

代码

Status

Development

Support