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

· · 题解

题目简述

给定长度为 n 正整数序列 a 和长度为 n 的由小写字母构成的字符串 S。对于 i\in[1,n]，如果 i\bmod2=1，则让 S_{1}\sim S_{i} 按字母表顺序向左移动 a_{i} 位；反之向右移动 a_{i} 位，最后输出 S。

特别地，a 向左移动变为 z，z 向右移动变为 a。

主要思路

由于共有 26 个字母，所以每移动 26 个字母就相当于没移动，我们可以将 a_{i}\gets a_{i}\bmod26。

对于 i\bmod2=1，我们可以理解为向右移动 -a_{i} 位，可以直接将其设为负数；对于每个字符的移动，其实就是 \sum_{j=i}^{n}a_{j}，这个和可以用前缀和求出。

但注意：z 处于 ASCII 码很后面的位置，所以当 z 加上一个数后，就有可能炸掉 char，那么就可以先用一个 int 变量来存储 S_{i} 移动后的 ASCII 码，再将 S_{i} 设为这个变量。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int N = 1e5 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
ll a[N], pre[N];
// ----------------------------

int main() {
    int n; cin >> n;
    string s; cin >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 26;
        if (i & 1) a[i] = -a[i];
        pre[i] = pre[i - 1] + a[i];
        pre[i] %= 26;
    }
    // ----------------------------
    for (int i = 0; i < n; i++) {
        int k = s[i] + (pre[n] - pre[i]) % 26;
        if (k > 'z') k -= 26;
        if (k < 'a') k += 26;
        s[i] = k;
    }
    // ----------------------------
    cout << s;
    return 0;
}