题解：B4303 [蓝桥杯青少年组省赛 2024] 字母移位

FJ_EYoungOneC · 2025-04-04 21:14:59 · 题解

解题思路

这里我们设置字符向右移动为正，往左移动为负。

第一个字符的移动次数为 a_1-a_2+a_3-a_4+\dots。

第二个字符的移动次数为 -a_2+a_3-a_4+\dots。

发现涉及大量重复计算，所以我们可以用后缀和来优化求和过程。

时间复杂度 O(n)。

AC_Code

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
string str;
int a[N];
LL s[N];

char move(char c, LL d)
{
    return ((c - 'a' + d) % 26 + 26) % 26 + 'a';
}

int main()
{
    cin >> n >> str;
    str = ' ' + str;

    for (int i = 1; i <= n; ++ i )
    {
        cin >> a[i];
        if (i & 1)
            a[i] = -a[i];
    }

    for (int i = n; i; -- i )
        s[i] = s[i + 1] + a[i];

    for (int i = 1; i <= n; ++ i )
        cout << move(str[i], s[i]);

    return 0;
}