CodeForces - 5C(思维+括号匹配)

题意

给出一个括号序列,求出最长合法子串和它的数量。 合法的定义:这个序列中左右括号匹配。

思路

这个题和普通的括号匹配有区别,并行的括号匹配也可以存在,比如()()(),这种答案就是长度为6。

葡京在线网投用一个数组记录每个位置是否匹配,用栈模拟,每遇到一个'('直接将下标入栈,遇到')'就看栈里面有没有'(',如果有就将这个位置和他匹配的位置(栈顶)置为10然后pop,没有就继续。

然后这个数组就是一片01了,找最长连续1即可,因为1表示这个位置可以匹配。

代码

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x & (-x))
int a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;
    stack<int> st;
    int l = s.length();
    for (int i = 0; i < l; i++)
    {
        if (s[i] == '(')
            st.push(i);
        else
        {
            if (st.size())
                a[st.top()] = a[i] = 1, st.pop();
        }
    }
    int mx = 0, cnt = 0;
    map<int, int> mp;
    for (int i = 0; i < l; i++)
    {
        if (a[i])
        {
            cnt++;
        }
        else
        {
            if (cnt >= mx)
            {
                mx = cnt;
                mp[mx]++;
            }
            cnt = 0;
        }
    }
    if (cnt >= mx)
        mx = cnt, mp[mx]++;
    if (mx == 0)
        mp[mx] = 1;
    cout << mx << " " << mp[mx] << endl;
    return 0;
}

  

posted @ 2019-12-12 13:39  MCQ1999  阅读(...)  评论(...)    收藏