小西和复制粘贴

NC215149. 小西和复制粘贴

描述

小西想写一个复制粘贴的工具帮她完成人均要参加的A+级竞赛。

给出参数 $S,n,m,k,a_i,b_i,c_i$ 。

现在给定一个只由小写字母组成的字符串 $S$ 作为初始内容，小西需要完成接下来的 $n$ 次操作。

每个操作由三个参数组成： $a_i,b_i,c_i$ ，表示复制S的第 $[a_i, b_i)$ 这一段字符串后插入到原字符串的 $c_i$ 位置，这里的索引都是0开始计算的，插入的意思是让复制的字符串的首位成为S的第 $c_i$ 位。

比如当 $S$ 为abcdef，操作为 $1,3,5$ 时，表示复制bc插入到第5个位置，所以结果为abcdebcf

此外，还给出一个最大长度 $m$ ，如果每次操作后 $S$ 的长度超过了 $m$ ，那么就只保留 $S$ 的前 $m$ 个字符。

比如当 $S$ 为abcdef， $m$ 为7，操作为 $1,3,5$ 时，表示复制bc插入到第5个位置，所以结果为abcdebcf，但长度超过了 $m$ ，所以结果变为abcdebc

小西想知道进行完这 $n$ 次操作后 $S$ 的前 $k$ 位的内容

输入描述

第一行输入两个整数和
第二行为字符串
第三行输入一个整数
接下来行每行三个整数依次表示






表示的长度。保证每次操作的参数对当前的合法。

输出描述

输出一行长度为的字符串表示操作完之后的前位的内容

示例1

输入:

2 18
abcdefghi
4
3 6 8
1 5 2
4 12 1
17 18 0

输出:

fa

示例2

输入:

输出:

adedbf

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 315ms, 内存消耗: 5252K, 提交时间: 2020-12-22 21:18:23

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll  n,k,m;
char s[2000005];
ll x[200005];
ll sum[200006];
ll a[200005];
ll b[200005];
ll c[200005];
int main(){
	cin >> k >> m;
	cin >> s;
	cin >> n;
	for(ll i = n-1;~i;i--){
		cin >> a[i] >> b[i] >> c[i];
	}
	for (ll i = 0;i < k;i++){
		ll p = i;
		for (ll j = 0;j < n;j++) if(c[j]<=p){
			ll tmp = b[j] - a[j];
			if (c[j] + tmp > p)p = a[j] + p - c[j];
			else p -= tmp;
		}
		cout << s[p];
	}
}

C(clang11) 解法, 执行用时: 198ms, 内存消耗: 2844K, 提交时间: 2020-12-22 22:43:53

#include<stdio.h>
#define MAX 200006
int k,m,n,a[MAX],b[MAX],c[MAX];
char s[MAX];
int main(void) {
	scanf("%d%d",&k,&m);
	scanf("%s",s);
	scanf("%d",&n);
	for(int i=n-1; ~i; i--) {
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	for(int i=0; i<k; i++) {
		int p=i;//找第p个字符
		for(int j=0; j<n; j++)
			if(c[j]<=p) {
				int len=b[j]-a[j];
				if(c[j]+len>p)
					p+=a[j]-c[j];
				else
					p-=len;
			}//c[j]比p大，不影响；比p小，要么取代p，要么让p的位置往前
		putchar(s[p]);
	}
	return 0;
}