自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 21:18:29，当前版本为作者最后更新于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;
}