CF5C Longest Regular Bracket Sequence

zrzring 2020-10-07 PM 30℃ 0条

找到最长的合法括号串,输出长度和出现次数

和CSP2019一样,开个栈把合法括号串的位置标为1,找最长的1串即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

void file() {
    freopen("std.in", "r", stdin);
    freopen("wa.out", "w", stdout);
}

const int N = 5e6 + 10, M = 2e6 + 10, inf = 1e9;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, ans, p[N], s[N], top, cnt;

char ch[N];

int main() {
    scanf("%s", ch + 1); n = strlen(ch + 1);
    for (int i = 1; i <= n; i++) {
        if (ch[i] == '(') s[++top] = i; else if (top) {p[s[top--]] = p[i] = 1;}
    }
    for (int i = 1; i <= n; i++) {
        int res = 0; while (p[i]) res++, i++;
        if (res > ans) ans = res, cnt = 1;
        else if (res == ans) cnt++;
    }
    printf("%d %d", ans, ans ? cnt : 1);
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00