(B卷,100分)- 字符串加密（Java & JS & Python & C）

题目描述

给你一串未加密的字符串str，通过对字符串的每一个字母进行改变来实现加密，加密方式是在每一个字母str[i]偏移特定数组元素a[i]的量，数组a前三位已经赋值：a[0]=1,a[1]=2,a[2]=4。

当i>=3时，数组元素a[i]=a[i-1]+a[i-2]+a[i-3]。

例如：原文 abcde 加密后 bdgkr，其中偏移量分别是1,2,4,7,13。

输入描述

第一行为一个整数n（1<=n<=1000），表示有n组测试数据，每组数据包含一行，原文str（只含有小写字母，0<长度<=50）。

输出描述

每组测试数据输出一行，表示字符串的密文。

用例

题目解析

首先是偏移量a[i]的计算，这里直接使用动态规划记忆化，具体实现看下面代码（这里有的人会用分治递归实时计算，也可以，看考虑内存还是时间了）

然后是字母的加密，这里字母加密其实就是s[i]的ASCII码 + a[i]，但是需要注意的是a[i]偏移量会超过26，即加密后就不是字母了，题目也没说怎么处理，我猜测加密后的字符串也应该都是小写字母组成，因此越界后需要环形处理，即z 偏移一位后变为 a，这里处理公式为：

(s[i] + ar[i] – 97) % 26 + 97

另外，本题还需要注意下，第50个字符的偏移量会达到10562230626642

这个值是超过int类型的，因此Java代码定义a数组时需要使用long[]类型。

而JS的整型安全值范围可以包含住10562230626642，Python则是天生支持大数（不进行除法的话），因此无需考虑整型溢出问题。

2023.08.06

优化:

本题的偏移量a[i]不应该让其无限制增大，虽然本题的字符串最长是50，但是如果可以更长的话，肯定会继续发生整型溢出。

由于每位字母偏移超过26就会回头，因此a[i]偏移量超过26意义不大，因此我们可以对a[i] %= 26，这样a[i]的大小就被限制在了26以内，且不会影响最终结果。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    String[] lines = new String[n];
    for (int i = 0; i < n; i++) {
      lines[i] = sc.next();
    }

    // 初始化a数组
    int[] a = new int[50];
    a[0] = 1;
    a[1] = 2;
    a[2] = 4;
    for (int i = 3; i < 50; i++) {
      a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26;
    }

    for (int i = 0; i < n; i++) {
      System.out.println(getResult(lines[i], a));
    }
  }

  public static String getResult(String str, int[] a) {
    // 为字符串的每一位字符添加a[i]偏移量
    char[] cArr = str.toCharArray();
    for (int i = 0; i < str.length(); i++) {
      cArr[i] = (char) ((a[i] + cArr[i] - 97) % 26 + 97);
    }
    return new String(cArr);
  }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length == n + 1) {
    lines.shift();
    lines.forEach((line) => console.log(getResult(line)));
    lines.length = 0;
  }
});

// 初始化a数组
const a = new Array(50);
a[0] = 1;
a[1] = 2;
a[2] = 4;
for (let i = 3; i < 50; i++) {
  a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26;
}

function getResult(str) {
  const cArr = [...str];
  // 为字符串的每一位字符添加a[i]偏移量
  return cArr
    .map((c, i) =>
      String.fromCharCode(((a[i] + c.charCodeAt() - 97) % 26) + 97)
    )
    .join("");
}

Python算法源码

# 输入获取
n = int(input())
lines = [input() for _ in range(n)]

# 初始化a数组
a = [0] * 50
a[0] = 1
a[1] = 2
a[2] = 4
for i in range(3, 50):
    a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26


# 算法入口
def getResult(s):
    ans = []

    # 为字符串的每一位字符添加a[i]偏移量
    for i in range(len(s)):
        ans.append((a[i] + (ord(s[i]) - 97)) % 26 + 97)

    return "".join(map(chr, ans))


# 算法调用
for i in range(n):
    print(getResult(lines[i]))

C算法源码

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);

    int a[50] = {1, 2, 4};

    for (int i = 3; i < 50; i++) {
        a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26;
    }

    for (int i = 0; i < n; i++) {
        char s[51];
        scanf("%s", s);

        for (int j = 0; j < strlen(s); j++) {
            s[j] = (char) ((a[j] + s[j] - 97) % 26 + 97);
        }

        puts(s);
    }

    return 0;
}