整个网站都在下雪特效怎么做,手机端h5网站模板下载,家装装饰设计,北京网络科技有限公司官网[语言月赛202303] String Problem P
题目描述
Farmer John 有 n n n 个字符串#xff0c;第 i i i 个字符串为 s i s_i si。
现在#xff0c;你需要支持如下 q q q 次操作#xff1a;
1 x y i#xff1a;把字符串 s x s_x sx 整体插入到字符串 s y s_y sy …[语言月赛202303] String Problem P
题目描述
Farmer John 有 n n n 个字符串第 i i i 个字符串为 s i s_i si。
现在你需要支持如下 q q q 次操作
1 x y i把字符串 s x s_x sx 整体插入到字符串 s y s_y sy 的第 i i i 个字符后更新 s y s_y sy。2 y求 s y s_y sy。
例如设 s 1 abc s_1 \texttt{abc} s1abc s 2 xyz s_2 \texttt{xyz} s2xyz则执行完 1 2 1 2 后把 s 2 s_2 s2 整体插入到 s 1 s_1 s1 的第 2 2 2 个字符后更新 s 1 s_1 s1 s 1 abxyzc s_1 \texttt{abxyzc} s1abxyzc s 2 xyz s_2 \texttt{xyz} s2xyz。
输入格式
第一行是两个整数表示字符串数量 n n n 和操作的数量 q q q。 接下来 n n n 行每行一个字符串第 i i i 行的字符串为 s i s_i si。 接下来 q q q 行每行四个或二个整数依次表示每次操作。具体格式见『题目描述』。
输出格式
对每次操作 2 2 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 % 60\% 60% 的数据保证 i ∣ s y ∣ i |s_y| i∣sy∣。对 100 % 100\% 100% 的数据 1 ≤ n , q ≤ 10 1 \leq n,q \leq 10 1≤n,q≤10 1 ≤ ∣ s i ∣ ≤ 10 1 \leq |s_i| \leq 10 1≤∣si∣≤10。 1 ≤ x , y ≤ n 1 \leq x, y \leq n 1≤x,y≤n 1 ≤ i ≤ ∣ s y ∣ 1 \leq i \leq |s_y| 1≤i≤∣sy∣。
其中 ∣ s y ∣ |s_y| ∣sy∣ 表示进行对应操作时 s y s_y sy 的长度 ∣ s i ∣ |s_i| ∣si∣ 表示输入时字符串的长度。
解析
这是一道关于字符串操作的题目,需要我们实现字符串的插入和查询功能。下面是使用C语言的解题思路和代码实现:
解题思路:
使用vector存储给定的n个字符串。对于操作1,将字符串sx插入到字符串sy的第i个字符后,可以使用string的insert方法实现。对于操作2,直接输出对应下标的字符串即可。
C代码实现:
#include iostream
#include vector
#include string
using namespace std;int main() {int n, q;cin n q;vectorstring 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;
}代码解释:
首先输入字符串的数量n和操作的数量q。创建一个vector类型的变量strings,用于存储给定的n个字符串。使用循环输入n个字符串,将它们存储到strings中。使用while循环处理q次操作: 如果操作类型为1,则输入x,y,i,并将下标减1(因为题目中的下标从1开始)。使用insert方法将字符串sx插入到字符串sy的第i个字符后。如果操作类型为2,则输入y,将下标减1,并输出对应下标的字符串。 程序结束,返回0。
时间复杂度分析:
设字符串的平均长度为L。对于操作1,插入操作的时间复杂度为O(L),因为插入操作需要移动字符串中的字符。对于操作2,输出操作的时间复杂度为O(L),因为需要输出整个字符串。总共有q次操作,因此总的时间复杂度为O(qL)。
空间复杂度分析:
使用vector存储n个字符串,每个字符串的平均长度为L,因此空间复杂度为O(nL)。
这个解法使用了vector和string类型,通过insert方法实现了字符串的插入操作,并直接输出对应下标的字符串来实现查询操作。如果你有任何其他问题或需要进一步的解释,请随时告诉我。
