题意

https://vjudge.net/problem/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;

}

巴特西

CodeForces - 5C（思维+括号匹配）

题意

思路

代码

最新文章

热门文章