Codeforces Round #138 (Div. 1) A : Bracket Sequence
問題概要
丸括弧と角括弧の列(L<1e5)の文字列が与えられる。括弧の対応がとれている部分文字列で、角括弧をもっとも多く含むものを具体的に求める問題。
解法
丸括弧と角括弧をそれぞれスタックに積んでいく。途中で括弧が足りなくなったり、対応してないものに当たったりしたら全部クリアすればよい。
acceptされたコード
#include <cstdio> #include <cstring> #include <algorithm> #include <stack> using namespace std; template<typename numType> inline bool updateMax(numType& old, const numType& test) { if (old < test) { old = test; return true; } return false; } const int MAX_L = int(1e5); char buf[MAX_L + 1]; int prevs[MAX_L + 1]; int accum[MAX_L + 1]; void init() { scanf("%s", buf); } void print(int maxi, int start, int last) { if (maxi <= 0) { puts("0\n"); return ; } else { printf("%d\n", maxi); for (int i = start; i < last; ++i) { putchar(buf[i]); } puts(""); } } void solve() { const int L = strlen(buf); for (int i = 0; i < L; ++i) { accum[i+1] = accum[i] + (buf[i] == '[' ? 1 : 0); } int maxi = 0, start = -1, last = -1; memset(prevs, -1, sizeof(prevs)); stack<int> S1, S2; for (int i = 0; i < L; ++i) { const char c = buf[i]; if (c == '[') { S1.push(i); } else if (c =='(') { S2.push(i); } else if(c == ']') { if (!S1.empty() && (S2.empty() || S2.top() < S1.top())) { prevs[i] = S1.top(); S1.pop(); } else { for (;!S1.empty();S1.pop()) ; for (;!S2.empty();S2.pop()) ; } } else if(c == ')') { if (!S2.empty() && (S1.empty() || S1.top() < S2.top())) { prevs[i] = S2.top(); S2.pop(); } else { for (;!S1.empty();S1.pop()) ; for (;!S2.empty();S2.pop()) ; } } } for (int i = L - 1 ; i >= 0; --i) { int l = prevs[i]; for (;l != -1 && l > 0 && prevs[l-1] != -1; l = prevs[l-1]); if (l != -1) { if (updateMax(maxi, accum[i+1] - accum[l])) { start = l; last = i + 1; } i = l - 1; } } print(maxi, start, last); } int main() { init(); solve(); return 0; }