ACM思維題訓練集合
A bracket sequence is a string, containing only characters “(”, “)”, “[” and “]”.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and “+” between the original characters of the sequence. For example, bracket sequences “()[]”, “([])” are correct (the resulting expressions are: “(1)+[1]”, “([1+1]+1)”), and “](” and “[” are not. The empty string is a correct bracket sequence by definition.

A substring s[l… r] (1?≤?l?≤?r?≤?|s|) of string s?=?s1s2… s|s| (where |s| is the length of string s) is the string slsl?+?1… sr. The empty string is a substring of any string by definition.

You are given a bracket sequence, not necessarily correct. Find its substring which is a correct bracket sequence and contains as many opening square brackets ?[? as possible.

Input
The first and the only line contains the bracket sequence as a string, consisting only of characters “(”, “)”, “[” and “]”. It is guaranteed that the string is non-empty and its length doesn’t exceed 105 characters.

Output
In the first line print a single integer — the number of brackets ?[? in the required bracket sequence. In the second line print the optimal sequence. If there are more than one optimal solutions print any of them.
Examples

Input
([])
Output
1
([])
Input
(((
Output
0
括號是就近匹配的，所以可以用棧來模擬，所以可以將括號壓棧，匹配后出棧，最后棧底剩余的就是不能出棧的就是不能匹配的，一般的方法是找到這些括號但是太費勁了，我們同時建立一個棧，同時入棧，出棧，存括號的下標，那么在出棧操作之后，第一個stack就只剩下不匹配的括號，第二個stack就只剩下不匹配的括號的下標。
下標將括號數(shù)組分成了好幾段，枚舉每一段的左中括號的數(shù)量即可，比較最大值更新左右段點即可

#include <bits/stdc++.h> using namespace std; template <typename t> void read(t &x) {char ch = getchar();x = 0;int f = 1;while (ch < '0' || ch > '9')f = (ch == '-' ? -1 : f), ch = getchar();while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();x *f; } #define wi(n) printf("%d ", n) #define wl(n) printf("%lld ", n) #define P puts(" ") typedef long long ll; #define MOD 1000000007 #define mp(a, b) make_pair(a, b) //---------------https://lunatic.blog.csdn.net/-------------------// const int N = 1e5 + 5; char a[N]; stack<char> m; stack<int> n; vector<int> x; int main() {scanf("%s", a);int ln = strlen(a);int cnt = 0;//cout<<ln<<endl;for (int i = 0; i < ln; i++){if (!m.size() || a[i] == '(' || a[i] == '['){m.push(a[i]);n.push(i);continue;}else if (a[i] == ')' && m.top() == '('){n.pop();m.pop();//cout << 1 << endl;}else if (a[i] == ']' && m.top() == '['){m.pop();n.pop();cnt++;// cout << 2 << endl;}else{m.push(a[i]);n.push(i);}}// cout<<1<<endl;if (m.empty()){wi(cnt);P;printf("%s\n", a);}else{x.push_back(ln);while (!n.empty()){x.push_back(n.top());n.pop();}x.push_back(-1);int ml, mr, maxi = 0;cnt = 0;for (int i = x.size() - 1; i > 0; i--){maxi = 0;// cout << x[i] + 1 << " " << x[i - 1] - 1 << endl;for (int j = x[i] + 1; j < x[i - 1]; j++){if (a[j] == '[')maxi++;}if (maxi > cnt){cnt = maxi;ml = x[i] + 1;mr = x[i - 1] - 1;}}wi(cnt);P;if (cnt == 0)return 0;for (int i = ml; i <= mr; i++){putchar(a[i]);}P;}//P; }

總結(jié)

以上是生活随笔為你收集整理的CF思维联系–CodeForces -224C - Bracket Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。