题目链接:
Codeforces 350 Div2 E Correct Bracket Sequence Editor
题意:
给出一个长度为偶数的只含’(‘和’)’并且两者个数相等的字符串,初始指针位置是p,下标从1开始.有三种操作:
R 指针位置右移,即p++
L 指针位置左移,即p–
D 删除p位置和相对应括号这个区间的所有括号
输出若干次操作后的字符串.
分析:
一开始用string模拟,果然TLE了,看到有人用list,需要预处理出每个括号和相对应的括号的下标.
第一次用list……
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <stack>
#include <list>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 500010;int match[MAX_N];int main()
{IOS;int n, m, p;while(cin >> n >> m >> p){string s1, s2;cin >> s1;cin >> s2;stack <int> s;for(int i = 0; i < n; i++){if(s1[i] == '('){s.push(i);}else {int t = s.top();s.pop();match[t] = i;match[i] = t;}}list <int> lis;for(int i = 0; i < n; i++) { lis.push_back(i); }list<int> ::iterator pos = lis.begin();for(int i = 1; i < p; i++) pos++;for(int i = 0; i < m; i++){if(s2[i] == 'L') pos--;else if(s2[i] == 'R') pos++;else {list<int> ::iterator tmp = pos;if(s1[*pos] == '('){while((*pos) != match[*tmp]) {pos++;}}else {while((*tmp) != match[*pos]) {tmp--;}}for(list<int> :: iterator it = tmp; it != pos; ){lis.erase(it++);}lis.erase(pos++);if(pos == lis.end()) pos--;}}for(list<int> :: iterator it = lis.begin(); it != lis.end(); it++){cout << s1[*it];}cout << endl;}return 0;
}