ClassicalStringProblem - 题解

标签与难度

标签: 字符串, 模拟, 数学, 取模运算, 循环数组, 思维题难度: 1200

题目大意喵~

主人你好呀，这道题是关于一个可爱的小写字母字符串 S 的说！我们需要对它进行 Q 次操作，操作有两种类型呐：

Modify (M x): 这是一个修改操作。
- 如果 x 是正数，就把字符串最左边的 x 个字符，像小猫打滚一样，滚到字符串的最右边去。比如 abcde 操作 M 2 后就变成 cdeab 啦。
- 如果 x 是负数，就把字符串最右边的 |x| 个字符，瞬移到最左边。比如 abcde 操作 M -2 后就变成 deabc 啦。
Answer (A x): 这是一个查询操作。
- 你需要回答，在当前状态下，字符串的第 x 个字符是什么（这里的 x 是从 1 开始数的哦）。

简单来说，就是对一个字符串进行循环移位，并随时回答某个位置上的字符是什么，喵~

解题思路分析

刚看到这道题，最直接的想法就是老老实实地按照题目的描述去移动字符串，对吧？但是呀，我们来想一想，如果字符串 S 特别长，比如有几十万个字符，每次 Modify 操作都真的去移动子串，那可就太慢啦！就像要把一团很长的毛线球重新整理一样，爪子都要累坏了喵~ 这种 $O(N \cdot Q)$ 的方法肯定会超时的说。

所以，我们需要一个更聪明的办法！

关键在于，我们得发现一个秘密：无论怎么旋转，字符串里的字符本身和它们的相对顺序是永远不变的。a 永远在 b 的前面（如果它们在环上的话），b 永远在 c 的前面，就像一个旋转木马，大家的位置是固定的，只是我们观察的起点变了而已。

既然如此，我们何必真的去移动字符串呢？我们只需要记录一下，"新"的字符串是从"旧"的字符串的哪个位置开始的，不就行了嘛？

我们可以用一个变量，比如说 shift_offset，来表示当前字符串的第一个字符，对应的是原始字符串的第几个位置（从0开始计数）。

初始状态: 字符串没有动过，所以 shift_offset = 0。
分析 Modify 操作 (M x):
- 当 x > 0 时，我们将最左边的 x 个字符移到右边。这相当于字符串向左旋转了 x 位。新的开头不就是原来第 x 个位置的字符嘛？所以，我们的 shift_offset 应该增加 x。
- 当 x < 0 时，我们将最右边的 |x| 个字符移到左边。这相当于字符串向右旋转了 |x| 位。向右旋转 |x| 位，等价于向左旋转 N - |x| 位 (其中 N 是字符串长度)。不过，我们也可以发现，向右旋转 |x| 位，其实就是把起始点向左移动 |x| 位，也就是 shift_offset 减去 |x|。因为 x 本身是负数，所以减去 |x| 就等于加上 x！
- 所以，不管是哪种情况，Modify 操作都可以统一成：shift_offset = shift_offset + x。
处理循环: 字符串是循环的，所以 shift_offset 可能会超出 [0, N-1] 的范围。这时候就需要我们的好朋友——取模运算 ％ 啦！每次更新后，我们都让 shift_offset 对字符串长度 N 取模，shift_offset = shift_offset % N。
一个重要的小陷阱！: 在 C++ 里，对负数取模的结果可能还是负数哦！比如 (-2) % 5 的结果是 -2。一个负数的偏移量可不好处理呢。为了让 shift_offset 始终保持在 [0, N-1] 这个可爱的范围里，我们可以用一个通用的小技巧：(a % n + n) % n。这样算出来的结果就一定是正数啦！所以，我们更新 shift_offset 的最终公式是：
$\text{shift\_offset} = ((\text{shift\_offset} + x) \% N + N) \% N$
分析 Answer 操作 (A x):
- 现在我们要找当前字符串的第 x 个字符（1-indexed）。
- 在当前字符串里，它的索引是 x - 1。
- 这个位置对应到原始字符串里的索引，就是从我们的 shift_offset 开始，再走 x - 1 步。
- 所以，它在原始字符串 S 里的索引就是 (shift_offset + x - 1)。
- 同样，为了防止越界，我们也要对 N 取模。所以最终的索引是：
$\text{final\_index} = (\text{shift\_offset} + x - 1) \% N$
因为我们保证了 shift_offset 是非负的，所以这里的取模就不用担心负数问题啦。

这样一来，每次操作都只是几次简单的整数加法和取模，时间复杂度是 $O(1)$ ！总的时间复杂度就是 $O(\text{len}(S) + Q)$ ，非常快，一定能顺利通过的，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮到你，呐~

cpp

#include <iostream>
#include <string>
#include <vector>
#include <cstdio> // 使用 scanf/printf 会更快一些喵
#include <cstring> // 使用 strlen

// 使用一个足够大的缓冲区来读取字符串，防止溢出
const int MAX_LEN = 2000005; 
char s[MAX_LEN];

int main() {
    // 为了加速C++的I/O，不过这里我们用C风格的I/O，所以不是必须的
    // std::ios_base::sync_with_stdio(false);
    // std::cin.tie(NULL);

    int q;
    // 读取初始字符串和操作次数
    scanf("%s %d", s, &q);

    int n = strlen(s);

    // 这个变量记录当前字符串的第一个字符在原始字符串中的偏移量
    // 把它想象成一个指向“新起点”的指针，喵~
    long long shift_offset = 0; 

    // 开始处理 Q 次操作
    for (int i = 0; i < q; ++i) {
        // 每次循环开始前，先用 getchar() 吃掉上一行留下的换行符
        // 这是混合使用 scanf("%d") 和 scanf("%c") 时常见的小技巧
        getchar(); 
        
        char op_type;
        int op_value;
        scanf("%c %d", &op_type, &op_value);

        if (op_type == 'M') {
            // --- 修改操作 ---
            // 无论是左移还是右移，都可以统一为偏移量的加法
            shift_offset += op_value;

            // 关键一步：处理循环和负数，确保偏移量总是在 [0, n-1] 范围内
            // (shift_offset % n + n) % n 是一个保证结果为正的模运算技巧
            shift_offset = (shift_offset % n + n) % n;

        } else { // op_type == 'A'
            // --- 查询操作 ---
            // 查询第 op_value 个字符（1-indexed），在当前视角下它的索引是 op_value - 1
            // 加上我们的偏移量，就得到了它在原始字符串 s 中的位置
            long long target_index = (shift_offset + op_value - 1) % n;
            
            // 输出结果，记得加换行符哦
            printf("%c\n", s[target_index]);
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N + Q)$
- $N$ 是初始字符串的长度。我们需要 $O(N)$ 的时间来读取字符串并计算它的长度（strlen）。
- $Q$ 是操作的次数。对于每一次操作，我们都只进行几次常数时间的算术运算。所以处理所有查询的总时间是 $O(Q)$ 。
- 加起来，总时间复杂度就是 $O(N + Q)$ ，非常高效的说！
空间复杂度: $O(N)$
- 我们需要一个字符数组来存储初始字符串 S，这占用了 $O(N)$ 的空间。
- 除此之外，我们只用了几个变量（如 q, n, shift_offset），它们只占用常数空间 $O(1)$ 。
- 所以总的空间复杂度由字符串本身决定，为 $O(N)$ 。

知识点总结

这道题虽然看起来是字符串操作，但核心却藏着一些数学小智慧呢，喵~

思维转换: 这是最重要的！不要被题目的表面描述（移动字符串）所迷惑，要深入思考操作的本质。将复杂的字符串操作转化为简单的数学运算（维护一个偏移量），是解决这类问题的关键。
循环数组/环形结构: 很多问题都可以抽象成环形结构。通过维护一个偏移量和使用模运算，我们可以在 $O(1)$ 的时间内模拟旋转和访问，而不需要真的移动数据。
模运算 (Modular Arithmetic): 它是处理周期性、循环性问题的强大工具。
- 核心用途: 将数值限制在一个固定的范围内，比如数组索引。
- 重要技巧: C++中负数取模的结果可能是负数。(a % n + n) % n 这个公式是处理这种情况的万能钥匙，能确保结果始终在 [0, n-1] 范围内。一定要记住它哦！
C++ I/O: 在处理大量输入输出的编程竞赛中，scanf/printf 通常比 cin/cout 快。如果混用 scanf("%d", ...) 和 scanf("%c", ...)，要小心换行符 \n 的问题，可以用 getchar() 来“吃掉”它。

希望这篇题解能对主人有所帮助，如果还有不明白的地方，随时可以再来问我哦，喵~

ClassicalStringProblem - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​