题解 CF1305B 【Kuroni and Simple Strings】
皎月半洒花
2020-03-06 08:11:33
发现显然删除一次和删除多次是等价的。那么只需要记录每个左括号和右括号的位置，找一个位置 $p$ 使得前面的左括号和右面的右括号一样多且最大。$0$ 的情况是存在某个 $p$ 使得 $p$ 前缀都是 `)` 并且 $p+1$ 后缀都是 `(` 。判断一下即可。
```cpp
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] << " " ;
}