华为OD机试B卷字符串加密解析（Python解法，附详细解题思路与满分攻略）

题目描述

给你一串未加密的字符串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）。

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

用例

字符串加密算法解析：如何通过动态偏移数组实现字符转换加密

1. 核心解题思路

1.1 问题拆解

要实现加密，需解决以下两个核心问题：

1. 生成偏移数组 a：
2. 根据递推公式计算每个位置的偏移量。
3. 关键点：处理大数问题（偏移量可能非常大）。
4. 字符偏移转换：
5. 将每个字符按对应的偏移量转换为新字符。
6. 关键点：字母循环处理（如 z 偏移 1 后应为 a）。

1.2 关键步骤

步骤1：生成偏移数组 a

步骤2：字符偏移转换

2. 代码实现与详细注释

Python代码

n = int(input())  # 读取测试用例数量
for _ in range(n):
    s = input().strip()  # 读取原文
    m = len(s)
    a = []  # 初始化偏移数组
    
    # 填充前三个元素（注意字符串长度可能小于3）
    if m >= 1:
        a.append(1)
    if m >= 2:
        a.append(2)
    if m >= 3:
        a.append(4)
    
    # 生成后续元素（i从3到m-1）
    for i in range(3, m):
        # 计算当前偏移量并取模26
        next_val = (a[i-1] + a[i-2] + a[i-3]) % 26
        a.append(next_val)
    
    # 加密每个字符
    encrypted = []
    for i in range(m):
        # 将字符转换为0-25的索引
        original_pos = ord(s[i]) - ord('a')
        # 计算新位置并取模26
        new_pos = (original_pos + a[i]) % 26
        # 转换回字符
        encrypted_char = chr(new_pos + ord('a'))
        encrypted.append(encrypted_char)
    
    # 输出结果
    print(''.join(encrypted))

代码解析

2.1 生成偏移数组 a

if m >= 1: a.append(1)
if m >= 2: a.append(2)
if m >= 3: a.append(4)

next_val = (a[i-1] + a[i-2] + a[i-3]) % 26

2.2 字符偏移转换

new_pos = (original_pos + a[i]) % 26

3. 复杂度分析

4. 优化与扩展

4.1 预计算偏移数组

4.2 大数处理的数学依据

a[i] = (a[i-1] + a[i-2] + a[i-3]) % 26

4.3 扩展功能

5. 测试与验证

测试用例1

1
xy

测试用例2

2
abcde
zzz

bdgkr
cba

6. 总结

通过动态规划生成偏移数组，并结合模运算处理字符循环，本方法能够高效解决字符串加密问题。代码实现中，通过逐层分解问题、边界条件处理和数学优化，确保了算法的正确性和性能。此思路还可扩展至其他需要周期性偏移的场景（如凯撒密码变种）。

作者：蜗牛的旷野