题解

题面描述

给定一个字符串 $s$，长度满足 $1 \le len(s) < 10^6$，由大小写字母混合构成。同时给定一个整数 $k$，代表需要进行的改造轮数，满足 $1 \le k \le 10^6$。

每一轮改造的规则如下：

• 对于每一个大写字母，将其修改为其字母表中前面的一位字母，特别地，'A' 的前一位为 'Z'；
• 对于每一个小写字母，将其修改为其字母表中后面的第 $i$ 位字母（$i$ 从 $1$ 开始），特别地，'z' 的后一位为 'a'。

要求输出经过第 $k$ 轮改造后的字符串。

问题本质分析

对一个字符连续进行多轮操作，本质上是对字符在字母表中的位置做加减，并对 $26$ 取模。记：

• 大写字母 'A' 到 'Z' 的编号为 $0$ 到 $25$；
• 小写字母 'a' 到 'z' 的编号为 $0$ 到 $25$。

每轮对大写字母做一次 $-1$ 操作，每轮对小写字母做一次 $+i$ 操作。进行 $k$ 轮后：

• 大写字母累计移动：$$-1 \times k \equiv -k \mod 26;$$
• 小写字母累计移动： $\sum_{i=1}^{k} i$ = $\frac{k(k+1)}{2}$ $\equiv$ $S$ $\mod 26.$ 其中 $S = \frac{k(k+1)}{2} \bmod 26$。

因此，只需要先计算好两个总位移量，然后对字符串中每个字符一次性转换。

• 若是大写字母 $c$，令原编号为 $x=c-'A'$，新编号为 $(x - k \bmod 26 + 26) \bmod 26$，再映射回字母；
• 若是小写字母 $c$，令原编号为 $y=c-'a'$，新编号为 $(y + S) \bmod 26$，再映射回字母；
• 其他字符保持不变（本题仅含字母）。

此方法时间复杂度 $O(n)$，空间复杂度 $O(n)$，完全满足 $n,k$ 达到 $10^6$ 时的要求。

思路

1. 读入字符串 $s$ 和整数 $k$。
2. 计算大写字母的总位移量 $U = (-k \bmod 26 + 26) \bmod 26$。这样可保证 $U$ 在 $0\ldots25$。
3. 计算小写字母的总位移量$$S = \Bigl(\frac{k(k+1)}{2} \bmod 26\Bigr).$$
4. 遍历字符串的每个字符：
   • 若是大写字母，计算新字符：$$\text{new} = 'A' + (c - 'A' + U) \bmod 26;$$
   • 若是小写字母，计算新字符：$$\text{new} = 'a' + (c - 'a' + S) \bmod 26;$$
   • 否则保持原字符。
5. 输出转换后的新字符串。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    long long k;
    cin >> s >> k;  // 读取字符串和轮数

    // 计算大写字母总位移量 U = -k mod 26
    int U = (int)(((-k) % 26 + 26) % 26);
    // 计算小写字母总位移量 S = k(k+1)/2 mod 26
    long long t = k * (k + 1) / 2;
    int S = (int)(t % 26);

    for (char &c : s) {
        if (c >= 'A' && c <= 'Z') {
            // 大写字母转换
            c = char('A' + (c - 'A' + U) % 26);
        } else if (c >= 'a' && c <= 'z') {
            // 小写字母转换
            c = char('a' + (c - 'a' + S) % 26);
        }
        // 其他字符不变（本题无此类）
    }

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

Python

# 读取输入
s = input().strip()
k = int(input())

# 计算位移量
U = ((-k) % 26 + 26) % 26  # 大写字母总位移
S = (k * (k + 1) // 2) % 26  # 小写字母总位移

# 构建结果列表
res = []
for c in s:
    if 'A' <= c <= 'Z':
        # 大写字母转换
        res.append(chr((ord(c) - ord('A') + U) % 26 + ord('A')))
    elif 'a' <= c <= 'z':
        # 小写字母转换
        res.append(chr((ord(c) - ord('a') + S) % 26 + ord('a')))
    else:
        res.append(c)

# 输出结果
print(''.join(res))

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();  // 读取字符串
        long k = Long.parseLong(br.readLine());  // 读取轮数

        // 计算位移量
        int U = (int) (((-k) % 26 + 26) % 26);  // 大写字母总位移
        long t = k * (k + 1) / 2;
        int S = (int) (t % 26);  // 小写字母总位移

        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                // 大写字母转换
                char nc = (char) ('A' + (c - 'A' + U) % 26);
                sb.append(nc);
            } else if (c >= 'a' && c <= 'z') {
                // 小写字母转换
                char nc = (char) ('a' + (c - 'a' + S) % 26);
                sb.append(nc);
            } else {
                sb.append(c);  // 其他字符不变
            }
        }

        System.out.println(sb.toString());
    }
}

题目内容

对于给定的字符串 $s$，将其进行 $k$ 轮改造，第 $i$ 轮改造的步骤如下：

• 对于每一个大写字母，将其修改为其字母表中前面的一位字母，特别的，'$A$’ 前面一位为 '$Z$’；

• 对于每一个小写字母，将其修改为其字母表中后面的第 $i$ 位字母($i$ 从 $1$ 开始)，特别的，'$z$ ’ 后面一位为'$a$ ’；

米小游想让你输出第 $k$ 轮改造后的字符串。

输入描述

第一行输入一个长度为 $1≤len(s)< 10^6$ ，由大小写字母混合构成的字符串 $s$ 。

第二行输入一个整数 $k(1 ≤k≤ 10^6)$ 代表需要改造的轮数。

输出描述

输出第 $k$ 轮改造后的字符串。

样例1

输入

WhilE
2

输出

UkloC

说明

在这个样例中：

第一轮改造，"$WhilE$" 变为 "$VijmD$"；

第二轮改造，"$VijmD$" 变为 "$UkloC$"。