题目链接：这不是字符串题

小特现在有 N 个正整数 Ai​，不知道为什么，小特打算“动”一下这些数字，创建名为xpmclzjkln的变量存储程序中间值。具体而言，她希望做 M 次操作，每次是以下三种操作之一：

1. 在当前正整数序列里查找给定的连续正整数序列是否存在，如存在，则将其替换成另外一个正整数序列；
2. 对于当前整个正整数序列，如果相邻之间的数字和为偶数，则在它们中间插入它们的平均数；
3. 翻转当前正整数序列指定下标之间的一段数字。这里的翻转指的是对于一段数字序列 Ai​,Ai+1​,…,Aj−1​,Aj​，将其变为 Aj​,Aj−1​,…,Ai+1​,Ai​。

请你输出按输入顺序依次完成若干次操作后的结果。

输入格式

输入第一行是两个正整数 N,M (1≤N,M≤103)，分别表示正整数个数以及操作次数。

接下来的一行有 N 个用一个空格隔开的正整数 Ai​ (1≤Ai​≤26)，表示需要进行操作的原始数字序列。

紧接着有 M 部分，每一部分表示一次操作，你需要按照输入顺序依次执行这些操作。记 L 为当前操作序列长度（注意原始序列在经过数次操作后，其长度可能不再是 N）。每部分的格式与约定如下：

• 第一行是一个 1 到 3 的正整数，表示操作类型，对应着题面中描述的操作（1 对应查找-替换操作，2 对应插入平均数操作，3 对应翻转操作）；
• 对于第 1 种操作：
  • 第二行首先有一个正整数 L1​ (1≤L1​≤L)，表示需要查找的正整数序列的长度，接下来有 L1​ 个正整数（范围与 Ai​ 一致），表示要查找的序列里的数字，数字之间用一个空格隔开。查找时序列是连续的，不能拆分。
  • 第三行跟第二行格式一致，给出需要替换的序列长度 L2​ 和对应的正整数序列。如果原序列中有多个可替换的正整数序列，只替换第一个数开始序号最小的一段，且一次操作只替换一次。注意 L2​ 范围可能远超出 L。
  • 如果没有符合要求的可替换序列，则直接不进行任何操作。
• 对于第 2 种操作：
  • 没有后续输入，直接按照题面要求对整个序列进行操作。
• 对于第 3 种操作：
  • 第二行是两个正整数 l,r (1≤l≤r≤L)，表示需要翻转的连续一段的左端点和右端点下标（闭区间）。

每次操作结束后的序列为下一次操作的起始序列。

保证操作过程中所有数字序列长度不超过 100N。题目中的所有下标均从 1 开始。

输出格式

输出进行完全部操作后的最终正整数数列，数之间用一个空格隔开，注意最后不要输出多余空格。

输入样例

39 5
14 9 2 21 8 21 9 10 21 5 4 5 26 8 5 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1
1
3 26 8 5
2 14 1
3
37 38
1
11 26 9 6 21 3 8 21 1 14 20 9
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2
3
2 40

输出样例

14 9 8 7 6 5 4 3 2 1 5 9 8 19 20 21 2 5 4 9 14 5 8 17 26 1 14 5 4 5 13 21 10 9 15 21 8 21 2 9 10 11 12 13 14 1 2

题目分析

比赛前看宣讲会直播就知道今年15分必有一个字符串题，做了前一个字符串题（这是字符串题）之后觉得不可能这么简单，看了下这两题的名字，再加上我对天梯赛出题老师尿性的理解，果然，这个题才是真正的字符串题！

其实就算没发现，题目中已经有暗示了：

接下来的一行有 N 个用一个空格隔开的正整数 Ai​ (1≤Ai​≤26)，表示需要进行操作的原始数字序列。

整数序列的范围是[1, 26]，就应该想到26个字母。

同时，题目要求的第1种操作，应该可以联想到string.find()和string.replace()函数，否则用vector等容器手写实现相对麻烦一些。

因此，如果这个题一开始就想到用string存储，就会做得非常轻松，否则会吃力费时一些。而且要知道，string本质就是元素为字符的存储容器（可以理解为字符数组）。

具体细节都写在下面代码注释里了，废话不多说😀

代码

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long

int main()
{
    int n, m;
    cin >> n >> m;

    string s(n, ' '); // 在string初始化直接开好长度，下同
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s[i] = x - 1 + 'a'; // 字符与数字之间的映射关系，下同
    }

    while (m--) {
        int op; // 操作指令
        cin >> op;
        if (op == 1) {
            // 操作1：查找与替换
            int l1, l2;
            cin >> l1;
            string s1(l1, ' ');
            for (int i = 0; i < l1; i++) {
                int x;
                cin >> x;
                s1[i] = x - 1 + 'a';
            }
            cin >> l2;
            string s2(l2, ' ');
            for (int i = 0; i < l2; i++) {
                int x;
                cin >> x;
                s2[i] = x - 1 + 'a';
            }
            int ind = s.find(s1); // 寻找s中是否有待匹配序列，如果没有，返回的是s.npos常量
            if (ind != s.npos) {
                // 如果有，直接替换。参数分别是：起始下标、替换掉的区间长度、待替换字符串（注意s2不会因为s1的长度而裁剪，正合题意）
                s.replace(ind, s1.length(), s2);
            }
        } else if (op == 2) {
            // 操作2：求平均数与插入
            for (int i = 0; i < s.length() - 1; i++) {
                // 下面这里虽然是需要判断数字之和是否为偶数，根据小学数学可证明，字符的Ascii码之和本题对应的数字之和奇偶性相同
                if ((s[i] + s[i + 1]) % 2 == 0) {
                    // 注意在s[i]的后面处插入，insert中的插入位置应该是i+1而不是1
                    s.insert(i + 1, 1, (s[i] + s[i + 1]) / 2); // 这里同样无需映射为数字求平均数后再映射为字符，直接求和即可
                    i++; // 注意在插入之后，直接跳过这个数字，以免重复操作（由题意和样例解释可推断）
                }
            }
        } else if (op == 3) {
            // 操作3：反转区间
            int l, r;
            cin >> l >> r;
            // string库本身没有反转函数，但是可以用reverse函数，注意参数是迭代器而不是下标
            reverse(s.begin() + l - 1, s.begin() + r); // 第二个参数是开区间右端点，因此无需再-1
        }
    }

    // 输出时再映射为数字
    for (int i = 0; i < s.length(); i++) {
        cout << (i ? " " : "") << s[i] - 'a' + 1;
    }

    return 0;
}

心得

这个题目比赛时是一眼看出来要用string了，相对还是比较顺利。

就是有些函数用法记不清了，现场写了个test.cpp测试用法。把reverse记错成reserve了，导致一直没跑出来🥲好在操作3直接用双指针就能出来，当时就手写了一个for循环去翻转。

比赛时中间有些小细节（比如区间边界、索引±1的问题）没一次AC，好在今年出题老师比较友善，给出了样例分步骤的结果，很快就发现了问题。相比前两年字符串题的体验还是好很多的😍

另外，在写题解调试的时候发现了出题人的小计计（最开始的输入映射为字符串后，用拼音读）：

经过第一次操作之后……

果然，不愧是天梯赛的尿性……😜