B3726 [语言月赛202303] String Problem P

[语言月赛202303] String Problem P

题目描述

Farmer John 有 $n$ 个字符串，第 $i$ 个字符串为 $s_i$。

现在，你需要支持如下 $q$ 次操作：

• 1 x y i：把字符串 $s_x$ 整体插入到字符串 $s_y$ 的第 $i$ 个字符后，更新 $s_y$。
• 2 y：求 $s_y$。

例如，设 $s_1=\text{abc}$，$s_2=\text{xyz}$，则执行完 1 2 1 2 后（把 $s_2$ 整体插入到 $s_1$ 的第 $2$ 个字符后，更新 $s_1$），$s_1=\text{abxyzc}$，$s_2=\text{xyz}$。

输入格式

第一行是两个整数，表示字符串数量 $n$ 和操作的数量 $q$。
接下来 $n$ 行，每行一个字符串，第 $i$ 行的字符串为 $s_i$。
接下来 $q$ 行，每行四个或二个整数，依次表示每次操作。具体格式见『题目描述』。

输出格式

对每次操作 $2$，输出一行一个字符串，表示被询问的串。

样例 #1

样例输入 #1

2 2
a
b
1 1 2 1
2 2

样例输出 #1

ba

样例 #2

样例输入 #2

3 6
abc
ijk
xyz
1 2 3 2
1 1 3 5
1 3 1 1
2 1
2 2
2 3

样例输出 #2

axyijkabczbc
ijk
xyijkabcz

提示

数据规模与约定

• 对 $60\%$ 的数据，保证 $i=|s_y|$。
• 对 $100\%$ 的数据，$1\le n,q\le 10$，$1\le |s_i|\le 10$。$1\le x,y\le n$，$1\le i\le |s_y|$。

其中 $|s_y|$ 表示进行对应操作时 $s_y$ 的长度，$|s_i|$ 表示输入时字符串的长度。

解析

这是一道关于字符串操作的题目,需要我们实现字符串的插入和查询功能。下面是使用C++语言的解题思路和代码实现:

解题思路:

1. 使用vector存储给定的n个字符串。
2. 对于操作1,将字符串sx插入到字符串sy的第i个字符后,可以使用string的insert方法实现。
3. 对于操作2,直接输出对应下标的字符串即可。

C++代码实现:

#include <iostream>
#include <vector>
#include <string>
using namespace std;int main() {int n, q;cin >> n >> q;vector<string> strings(n);for (int i = 0; i < n; i++) {cin >> strings[i];}while (q--) {int op;cin >> op;if (op == 1) {int x, y, i;cin >> x >> y >> i;x--, y--, i--;strings[y].insert(i, strings[x]);} else if (op == 2) {int y;cin >> y;y--;cout << strings[y] << endl;}}return 0;
}

代码解释:

1. 首先输入字符串的数量n和操作的数量q。
2. 创建一个vector类型的变量strings,用于存储给定的n个字符串。
3. 使用循环输入n个字符串,将它们存储到strings中。
4. 使用while循环处理q次操作:
   • 如果操作类型为1,则输入x,y,i,并将下标减1(因为题目中的下标从1开始)。使用insert方法将字符串sx插入到字符串sy的第i个字符后。
   • 如果操作类型为2,则输入y,将下标减1,并输出对应下标的字符串。
5. 程序结束,返回0。

时间复杂度分析:

• 设字符串的平均长度为L。
• 对于操作1,插入操作的时间复杂度为O(L),因为插入操作需要移动字符串中的字符。
• 对于操作2,输出操作的时间复杂度为O(L),因为需要输出整个字符串。
• 总共有q次操作,因此总的时间复杂度为O(qL)。

空间复杂度分析:

• 使用vector存储n个字符串,每个字符串的平均长度为L,因此空间复杂度为O(nL)。

这个解法使用了vector和string类型,通过insert方法实现了字符串的插入操作,并直接输出对应下标的字符串来实现查询操作。如果你有任何其他问题或需要进一步的解释,请随时告诉我。