P2492. 字符串加密

解题思路

偏移量数组的计算

第 i 个字符（i >= 3）的偏移量实际上符合 泰波那契数列，可以很容易地求出偏移量数组 OFFSETS。

由于题目要求输入 n 组用例，而每一次用的偏移量数组 OFFSETS 都是同一个，因此只需要 提前求一次偏移量数组 即可进行复用。

特别注意，对于 Java、C++ 等语言，泰波那契数列在取到 n = 50 时会出现 整型范围溢出 的问题，可以在构造 OFFSETS 数组的时候对 26 进行取模以避免该问题。

单个字符的加密

对于特定的字符 ch 的加密，需要用到 ord()、chr()、求模 等基础语法知识。

ord(ch) - ord("a") 可以计算得到字符 ch 和字母 "a" 之间的距离，加上偏移量 offset 并对 26 取模可以得到偏移后的字符和字母 "a" 之间的距离，加上 ord("a") 之后可以得到偏移后的字母的 ASCII 码值，最终再取 chr() 可以将 ASCII 码值转化为字母本身。

复杂度分析 设用例组数为 n，单个字符串的长度为 L（由代码注释可知本题串长上限为 50，偏移表按 50 预建）。

• 预处理偏移量数组 OFFSETS：长度固定为 50 的一次线性递推，为 O(50)，可视为常数；由于 n 组用例共用同一张偏移表，这一步只做一次，这正是把它放在读入 n 之前、循环之外的原因。
• 每组用例调用 convert：对字符串逐字符调用 help，每个字符只做一次减法、一次加法和一次取模，均为 O(1)；用 StringBuilder 追加结果，避免了反复拼接字符串的额外开销，单组为 O(L)。
• 总时间复杂度为 O(n·L)，即与全部输入的字符总数成正比，这已是必须读完所有输入的下界量级。

空间上，OFFSETS 数组固定为 O(50)，每组用例的 StringBuilder 需要 O(L)，总空间复杂度为 O(L)（不计输出本身）。另外，递推时对 26 取模不改变加密结果——偏移本来就是在模 26 意义下生效的——却把数值压在 int 范围内，既是防溢出的手段，也保证了偏移表可以安全复用。