Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor 模拟

题目链接:

http://codeforces.com/contest/670/problem/E

题解:

用STL的list和stack模拟的,没想到跑的还挺快。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<list>
#include<stack>
using namespace std; const int maxn = + ;
const int INF = 2e9;
typedef __int64 LL; int n, m, pos;
char str[maxn];
list<char> ml;
stack<char> ms; void init() {
ml.clear();
} int main() {
while (scanf("%d%d%d", &n, &m, &pos) == && n) {
pos--;
init();
scanf("%s", str);
for (int i = ; i < n; i++) {
ml.push_back(str[i]);
}
scanf("%s", str);
list<char>::iterator it = ml.begin();
while (pos--) ++it;
for (int i = ; i < m; i++) {
if (str[i] == 'L') it--;
else if (str[i] == 'R') it++;
else {
ms.push(*it);
list<char>::iterator p = it;
if (*p == '(') {
while (!ms.empty()) {
++p;
if (ms.top() == '('&& *p == ')') ms.pop();
else ms.push(*p);
}
++p;
it = ml.erase(it, p);
}
else {
while (!ms.empty()) {
--p;
if (*p == '('&&ms.top() == ')') ms.pop();
else ms.push(*p);
}
++it;
it = ml.erase(p, it);
}
if (it == ml.end()) --it;
}
}
for (it = ml.begin(); it != ml.end(); it++) printf("%c", *it);
printf("\n");
}
return ;
}
上一篇:List的对比


下一篇:cf670E Correct Bracket Sequence Editor