题目

U736965 凯撒密码变体 – 洛谷

题解

题目给定一个长度为 $n$ 的字符串 $s$，以及 $26$ 个整数 $a_1,a_2,\ldots,a_{26}$，分别表示字母 a 到 z 的偏移量，要求我们按照每个字母对应的偏移量对字符串进行加密，并输出加密后的字符串。

首先需要注意，题目中的偏移量是针对每一种字母的，而不是针对字符串中的每一个位置。例如，假设字母 a 的偏移量为 $2$，那么无论 a 在字符串中出现多少次，都应该被加密为 c。

我们知道，在 C++ 中，小写字母 a 到 z 的字符编码是连续的，因此可以通过 s[i] - 'a' 将一个小写字母转换为 $0$ 到 $25$ 之间的整数。例如，a 对应 $0$，b 对应 $1$，以此类推，z 对应 $25$。

这样我们就可以使用一个长度为 $26$ 的数组 $a$ 来存储每个字母的偏移量。对于当前字符 $s[i]$，设其对应的编号为 $x$，那么它的偏移量就是 $a[x]$。

接下来考虑如何处理字母的循环位移。由于字母表中只有 $26$ 个小写字母，当一个字母向后移动超过 z 时，需要重新从 a 开始。因此我们可以使用取模运算来解决这个问题，加密后的字母编号为：

$$
y=(x+a[x])\bmod 26
$$

例如，字母 z 对应的编号为 $25$，假设它的偏移量为 $2$，那么加密后的编号为 $(25+2)\bmod 26=1$，也就是字母 b。

得到新的编号 $y$ 后，只需要通过 'a' + y 将其转换回对应的字符即可。

因此，我们只需要从左到右遍历整个字符串，对于每个字符先计算其原始编号，再根据该字母对应的偏移量计算加密后的编号，最后直接修改字符串中对应位置的字符。

由于每个字符只需要进行常数次运算，整个算法的时间复杂度为 $O(n)$。我们只使用了一个长度为 $26$ 的数组存储偏移量，并直接在原字符串上修改，因此不计输入字符串本身，额外空间复杂度为 $O(1)$，显然可以通过此题。

#include <bits/stdc++.h>

using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;

void solve()
{
    int n; cin >> n;
    string s; cin >> s;

    int a[26];
    for (int i = 0; i < 26; ++i)
    {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i)
    {
        int x = s[i] - 'a';
        s[i] = char('a' + (x + a[x]) % 26);
    }

    cout << s << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}