题目链接：洛谷 Codeforces
题目描述
最近，Polycarp开始开发一种仅适用于正确括号序列（缩写为CBS）的文本编辑器。请注意，如果可以通过添加“+”-s和“1”-s来获得正确的数学表达式，则括号序列是正确的。例如，序列“（（））（）”“（）”和“（（）（（）））”是正确的，而“）（”“（（）”和“（（）））（”是不正确的。CBS中的每个括号都有一对。例如，在“（（）（（）））”中：
第1个括号与第8个括号配对，
第2个括号与第3个括号配对，
第3个括号与第2个括号配对，
第4个括号与第7个括号配对，
第5个括号与第6个括号配对，
第6个括号与第5个括号配对，
第7个括号与第4个括号配对，
第8个括号与第1个括号配对。
Polycarp的编辑器目前在使用CBS期间仅支持三种操作。编辑器中的光标占据其中一个括号的整个位置（而不是括号之间的位置！）。支持三种操作：
«L»-将光标向左移动一个位置，
«R»-将光标向右移动一个位置，
«D»-删除光标所在的括号，删除与其配对的括号以及它们之间的所有括号（即，删除光标所在的括号和与其配对的括号之间的子字符串）。
操作“D”后，光标移动到最右边的括号中（当然，在未删除的括号中）。如果没有这样的括号（即，CBS的后缀已被删除），则光标将移动到最靠近左侧的括号（当然，在未删除的括号中）。
下面的图片说明了操作“D”的几种用法。
Polycarp的编辑器不支持所有不正确的操作（将光标移到CBS的末尾，删除整个CBS等）。
Polycarp对他的开发感到非常自豪，你能实现他的编辑器的功能吗？
输入：
第一行包含三个正整数n、m和p（2≤N≤500000, 1≤M≤500000, 1≤P≤n）——正确括号顺序中括号的数量、操作的数量和光标的初始位置。序列中的位置从左到右编号，从1开始。保证n是偶数。
它后面是由n个字符组成的字符串“（“和”）”，构成正确的括号序列。
然后跟随一个由m个字符组成的字符串“L”“R”和“D”——一系列操作。从第一个到最后一个，一个接一个地进行操作。可以保证给定的操作不会将光标移到括号序列之外，并且在所有操作之后，括号序列将是非空的。
输出：
打印正确的括号顺序，这是对初始顺序应用所有操作后获得的结果。
样例输入1
8 4 5
(())()()
RDLD
样例输出1
()
样例输入2
12 5 3
((()())(()))
RRDLD
样例输出2
(()(()))
样例输入3
8 8 8
(())()()
LLLLLLDD
样例输出3
()()
提示：
在第一个样例中，光标最初位于位置5。考虑编辑的过程：命令“R”-光标移动到右侧的位置6；命令“D”-从位置5到位置6删除括号。在CBS采取形式（（））（）之后，光标位于位置5；命令“L”-光标移动到左侧的位置4；命令“D”-从位置1到位置4删除括号。在CBS采用（）形式之后，光标位于位置1。
因此，答案等于（）。
代码&注释部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,p;
char c;
list<char> a;
cin>>n>>m>>p;
a.push_back('!');
for (int i=1;i<=n;i++) {
cin>>c;
a.push_back(c);
}
list<char>::iterator it;
list<char>::iterator posBeg,posEnd;
list<char>::iterator temp;
it=a.begin();
it++;
for (int i=2;i<=p;i++) it++;
for (int i=1;i<=m;i++) {
cin>>c;
if (c=='R') it++;
if (c=='L') it--;
if (c=='D') {
if (*it=='(') {
posBeg=it;
posEnd=it;
posEnd++;
int cnt=1;
for (temp=posEnd;temp!=a.end();temp++) {
if (*temp=='(') cnt++;
if (*temp==')') cnt--;
if (cnt==0) break;
}
posEnd=temp;
posEnd++;
temp=posEnd;
if (temp==a.end())
it--;
else it=temp;
for (temp=posBeg;temp!=posEnd;)
a.erase(temp++);
}
else if (*it==')') {
posBeg=it;
posEnd=it;
posBeg--;
int cnt=1;
for (temp=posBeg;temp!=a.begin();temp--) {
if (*temp==')') cnt++;
if (*temp=='(') cnt--;
if (cnt==0) break;
}
posBeg=temp;
posEnd++;
temp=posEnd;
if (temp==a.end()) {
it=posBeg;
it--;
}
else it++;
for (temp=posBeg;temp!=posEnd;)
a.erase(temp++);
}
}
}
temp=a.begin();
temp++;
for (it=temp;it!=a.end();it++)
cout<<*it;
return 0;
}
|
花絮&起因
由于Titan让我做翻译&做测试数据
于是我生产了以下不忍直视的随机数生成程序
好玩の随机数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
int main()
{
srand((int)time(0));
int n,m,p;
n=rand()%250;
n*=2;
m=rand()%100;
m*=2;
p=rand()%n;
cout<<n<<' '<<m<<' '<<p<<endl;
int cnt;
string s;
do {
cnt=0;
s="";
for (int i=1;i<=n;i++) {
char c;
c='('+rand()%2;
if (c=='(') cnt++;
else cnt--;
if (cnt==-1) {
cnt+=2;
c='(';
}
s=s+c;
}
}while (cnt!=0);
cout<<s<<endl;
for (int i=1;i<=m;i++) {
int k=rand()%3;
if (k==0) cout<<"L";
else if (k==1) cout<<"R";
else cout<<"D";
}
cout<<endl;
return 0;
}
|
心得&解释
- 题目很长，翻译成中文1100字，不过废话很多。
- 狠狠地体验了迭代器的运用。并使用了对头部和尾部的特殊操作。
- coding完之后，过了样例以后有点开心，交上去TLE的绝望。之后想挣扎，把整个程序写了个注释，还是没有AC。之后询问了某位大佬，他告诉我是迭代器失效的问题。（虽然这个问题我在前面部分尽力规避了，但还是在最后erase的部分出了岔子。把for()中的递增语句移到循环体中，就可以防止迭代器失效的问题。）
- 在制作数据的过程中，学到了随机数、文件读写的运用。难点是括号部分完全匹配以及题中的三个指令使得指针不越界。我在随机数生成程序中完成了用循环强制进行括号匹配，由于我源代码的特性，使得指针越界操作直接使程序无法运行，可以保证生成的指令序列合法。
