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

· · 题解

思路

根据题意，我们知道，左移表示 ASCII 码相减，右移表示 ASCII 码相加，所以将左移记为负，右移记为正。
根据题意，我们发现：
若 i 为奇，第 i 个字符的 ASCII 码变化为 a_i-a_{i+1}+a_{i+2}-a_{i+3}+a_{i+4}\ldots a_n；
若 i 为偶，第 i 个字符的 ASCII 码变化为 -a_i+a_{i+1}-a_{i+2}+a_{i+3}-a_{i+4}\ldots a_n=-(a_i-a_{i+1}+a_{i+2}-a_{i+3}+a_{i+4}\ldots a_n)。
因为 1\le n\le 10^5，暴力会超时，所以用后缀和进行优化，时间复杂度 O(n)，可以通过此题。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n,a[100005];
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=n;i>=1;--i){
        a[i]-=a[i+1]-26;
        a[i]%=26;
        //后缀和
        //为了后面计算方便，取模一下吧！
        //取模时注意避免负数
    }
    for(int i=1;i<=n;++i){
        if(i%2)s[i-1]=(s[i-1]-'a'-a[i]+26)%26+'a';//为奇，减
        else s[i-1]=(s[i-1]-'a'+a[i]+26)%26+'a';//为偶，加
        //注意取模，注意避免负数
    }
    cout<<s<<"\n";
    return 0;
}