笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 CF1305B 【Kuroni and Simple Strings】

posted on 2020-03-06 08:11:33 | under 题解 |

发现显然删除一次和删除多次是等价的。那么只需要记录每个左括号和右括号的位置,找一个位置 $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] << " " ;
}