比赛场次 398
比赛名称 20151028a
比赛状态 已结束比赛成绩
开始时间 2017-09-19 19:00:00
结束时间 2017-09-19 22:00:00
开放分组 全部用户
注释介绍
题目名称 复制&粘贴
输入输出 copypaste.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 26 简单对比
用户 结果 时间 内存 得分
Gravatar奥、神代号~ AAAAAAAAAAAAAAAAAAAA
AAAAAA
2.332 s 3.56 MiB 100
GravatarShirry AAAAAAAAAAAAAAAAAAAA
AAAAAA
2.773 s 2.77 MiB 100
GravatarAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA
AAAAAA
2.781 s 1.93 MiB 100
GravatarArrow AAAAAAAAAAAAAAAAAAAA
AAAAAA
3.208 s 2.48 MiB 100
Gravatar实力演员阵容 AAAAAAAAEEEEEEEEEETE
EEEEEE
3.506 s 10.78 MiB 30
GravatarFisher. AAAAAAAAEEEEEEEEEETE
EEEEEE
5.957 s 0.31 MiB 30

复制&粘贴

★★   输入文件:copypaste.in   输出文件:copypaste.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


文本编辑器的一个最重要的机能就是复制&粘贴。JOI社现在正在开发一款能够非常高速地进行复制&粘贴的文本编辑器,作为JOI社一名优秀的程序猿,你担负起了复制&粘贴功能的测试这一核心工作。整个JOI社的命运都系在你的身上,因此你无论如何都想写出一个正确且高速的程序来完成这项工作。

具体的做法如下所示。文件的内容是一个字符串S,对其进行N次复制&粘贴的操作,第i次操作复制位置Ai和位置Bi之间的所有文字,然后在位置Ci粘贴。这里位置x表示字符串的第x个字符的后面那个位置(位置0表示字符串的开头),例如字符串”copypaste”的位置6表示字符’a’和字符’s’之间的位置,位置9表示’e’后面的位置(即字符串的结尾)。不过,如果操作后的字符串长度超过了M,那么将超过的部分删除,只保留长度为M的前缀。

你的任务是写一个程序,输出N次操作后字符串的前K个字符。


【输入格式】


第一行两个空格分隔的正整数K和M,表示最终输出的文字数量和字符串长度的上限。

第二行一个字符串S,表示初始的字符串。

第三行一个整数N,表示操作的次数。

接下来N行,第i行包含三个空格分隔的整数Ai,Bi,Ci,表示第i次操作将位置Ai到Bi之间的字符串复制,然后粘贴到位置Ci。


【输出格式】

输出一行一个长度为K的字符串,表示最终的字符串的长度为K的前缀

【样例输入】

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

【样例输出】

ac

【提示】


初始的字符串为”copypaste”。

第一次操作将从位置3到位置6的字符串”ypa”复制,插入位置8,得到字符串”copypastypae”

第二次操作将从位置1到位置5的字符串”opyp”复制,插入位置2,得到字符串”coopyppypastypae”

第三次操作将从位置4到位置12的字符串”yppypast”复制,插入位置1,得到字符串”cyppypastoopyppypastypae”,由于长度超过了M=18,删除超过的部分,得到”cyppypastoopyppypa”

第四次操作将从位置17到位置18的字符串”a”复制,插入位置0,得到字符串”acyppypastoopyppypa”,删除超过18的部分得到”acyppypastoopyppyp”

最后输出长度为2的前缀”ac”即为答案。




对于40%的数据,N,M<=2000

对于100%的数据:

1<=K<=200

1<=M<=10^9

S的每个字符都是小写字母(‘a’~’z’)

K<=|S|<=min(M,2*10^5)

1<=N<=2*10^5

设第i次操作前的字符串长度为Li,那么0<=Ai<Bi<=Li且0<=Ci<=Li (1<=i<=N)


【来源】

在此键入。