题解 CF1305B 【Kuroni and Simple Strings】

皎月半洒花 · 2020-03-06 08:11:33 · 题解

发现显然删除一次和删除多次是等价的。那么只需要记录每个左括号和右括号的位置，找一个位置 p 使得前面的左括号和右面的右括号一样多且最大。0 的情况是存在某个 p 使得 p 前缀都是 ) 并且 p+1 后缀都是 ( 。判断一下即可。

int main(){
    cin >> (s + 1) ;
    int n = strlen(s + 1) ;
    for (int i = 1 ; i <= n ; ++ i){
        if (s[i] == '(') l[++ l[0]] = i, sum[i] = sum[i - 1] ;
        if (s[i] == ')') r[++ r[0]] = i, sum[i] = sum[i - 1] + 1 ;
    }
    for (int i = 0 ; i <= n ; ++ i)
        if (sum[i] == i && sum[i] == sum[n]) return puts("0"), 0 ;
    int L = 1, R = r[0] ;
    while (1){
        if (l[L] > r[R]) break ; ++ ans;
        stk[++ tp] = l[L], stk[++ tp] = r[R] ;
        L ++ ; R -- ; if (L > l[0] || !R) break ;
    }
    sort(stk + 1, stk + tp + 1) ;
    cout << 1 << endl << ans * 2 << endl ;
    for (int i = 1 ; i <= ans * 2 ; ++ i) cout << stk[i] << " " ;
}