CF 917A The Monster

题目描述

https://codeforces.com/problemset/problem/917/A

简要题意：给定一个包含 $?$ 的长度为 $n$ 的括号序列，求有多少子区间 $[l,r]$ 可以通过将 $?$ 转换成 $($ 或 $)$ 变成一个合法的括号序列

$n\le 3000$

Solution

如果区间 $[l,r]$ 合法，那么一定有对于 $[l,r]$ 中的任何一个前缀，都存在 $(+?\ge)$，任何一个后缀都存在 $)+?\ge($

那么我们对于每个左端点预处理出最长合法的右端点，每个右端点预处理出最长合法的左端点即可

时间复杂度 $O(n^2)$

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 5010
using namespace std;

int n; 

char s[maxn];

int l[maxn], r[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        int p = i, sum = 0;
        while (sum >= 0 && p <= n) {
            if (s[p++] == ')') --sum;
            else ++sum;
        } l[i] = p - 1;
    }
    for (int i = 1; i <= n; ++i) {
        int p = i, sum = 0;
        while (sum >= 0 && p >= 1) {
            if (s[p--] == '(') --sum;
            else ++sum;
        } r[i] = p + 1; 
    } int ans = 0; 
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= l[i]; ++j)
            if (r[j] <= i && j - i & 1) ++ans;
    cout << ans << "\n"; 
    return 0;
}