L1-6 这不是字符串题

loopdeloop

已于 2025-04-30 09:28:59 修改

阅读量972

点赞数 13

文章标签：算法

于 2025-04-30 09:25:24 首次发布

本文链接：https://blog.csdn.net/loopdeloop/article/details/147624993

版权

因为每年天梯赛字符串题的解答率都不尽如人意，因此出题组从几年前开始决定：每年的天梯赛的 15 分一定会有一道字符串题，另外一道则一定不是字符串题。

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

在当前正整数序列里查找给定的连续正整数序列是否存在，如存在，则将其替换成另外一个正整数序列；
对于当前整个正整数序列，如果相邻之间的数字和为偶数，则在它们中间插入它们的平均数；
翻转当前正整数序列指定下标之间的一段数字。这里的翻转指的是对于一段数字序列 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

样例解释:

为方便大家理解题意和调试程序，以下为样例每一步的中间操作序列结果：
第 1 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1

注意这里只会替换第一次的序列。
第 2 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 1 2

第 3 次操作结束后：

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

第 4 次操作结束后：

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

题目概述

这道题目虽然标题说"这不是字符串题"，但实际上是一道关于序列操作的题目。我们需要对给定的正整数序列执行三种操作：

查找替换操作：查找给定的连续子序列，如果存在则替换为另一个序列
插入平均数操作：在相邻数字和为偶数的位置插入它们的平均数
翻转操作：翻转指定区间的子序列

解题思路

数据结构选择

由于序列长度在操作过程中会动态变化（最大不超过100N），我们选择使用数组来存储序列，并维护当前序列长度。

操作实现

操作1：查找替换

读取要查找的子序列和目标替换序列
遍历当前序列，寻找第一个匹配的子序列
如果找到，执行替换操作：
- 将原序列分成三部分：匹配点前、替换序列、匹配点后
- 合并这三部分形成新序列
更新序列长度

操作2：插入平均数

遍历当前序列，检查每对相邻数字
如果和为偶数，在它们之间插入平均数
使用临时数组存储新序列
更新序列长度

操作3：翻转操作

读取要翻转的区间[l, r]
将区间内的元素顺序反转
使用临时数组辅助完成翻转

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

int D[1000005];
int C[1000005];

int main() {
    int a, b;
    cin >> a >> b;
    for(int i = 1; i <= a; i++) {
        cin >> D[i];
    }
    
    for(int op = 1; op <= b; op++) {
        int t;
        cin >> t;
        
        if(t == 2) { // 插入平均数操作
            int flag = 1;
            C[flag] = D[1];
            flag++;
            for(int i = 2; i <= a; i++) {
                if((D[i] + D[i-1]) % 2 == 0) {
                    C[flag] = (D[i] + D[i-1]) / 2;
                    flag++;
                    C[flag] = D[i];
                    flag++;
                } else {
                    C[flag] = D[i];
                    flag++;
                }
            }
            // 更新序列
            for(int i = 1; i < flag; i++) {
                D[i] = C[i];
            }
            a = flag - 1;
            
        } else if(t == 1) { // 查找替换操作
            int n;
            cin >> n;
            int G[500005];
            for(int i = 1; i <= n; i++) {
                cin >> G[i];
            }
            int m;
            cin >> m;
            int E[500005];
            for(int i = 1; i <= m; i++) {
                cin >> E[i];
            }
            
            int flag2 = 0;
            for(int i = 1; i <= a; i++) {
                if(D[i] == G[1]) {
                    int flag1 = 0;
                    for(int j = 2; j <= n; j++) {
                        if(D[i+j-1] != G[j]) {
                            flag1 = 1;
                            break;
                        }
                    }
                    if(flag1 == 1) continue;
                    
                    // 执行替换
                    int flag = i;
                    for(int j = 1; j <= i-1; j++) {
                        C[j] = D[j];
                    }
                    for(int j = 1; j <= m; j++) {
                        C[flag] = E[j];
                        flag++;
                    }
                    for(int j = i+n; j <= a; j++) {
                        C[flag] = D[j];
                        flag++;
                    }
                    flag2 = 1;
                    
                    // 更新序列
                    for(int k = 1; k < flag; k++) {
                        D[k] = C[k];
                    }
                    a = flag - 1;
                }
                if(flag2 == 1) break;
            }
            
        } else if(t == 3) { // 翻转操作
            int l, r;
            cin >> l >> r;
            
            // 复制前部分
            for(int i = 1; i < l; i++) {
                C[i] = D[i];
            }
            // 翻转中间部分
            int flag = l;
            for(int j = r; j >= l; j--) {
                C[flag] = D[j];
                flag++;
            }
            // 复制后部分
            for(int i = r+1; i <= a; i++) {
                C[i] = D[i];
            }
            // 更新序列
            for(int i = 1; i <= a; i++) {
                D[i] = C[i];
            }
        }
    }
    
    // 输出结果
    for(int i = 1; i <= a; i++) {
        if(i != 1) cout << " " << D[i];
        else cout << D[i];
    }
    
    return 0;
}