题解 CF1305B 【Kuroni and Simple Strings】
xht
2020-03-06 13:15:51
要求最终不能再存在 `()` 这样的子串,因此只能是若干个 `)` 后接若干个 `(`。
因此我们要找到一个位置,这个位置左边的 `(` 全部被删掉,右边的 `)` 全部被删掉。
由于只能删掉同等数量的 `(` 和 `)`,而这个位置一定存在,因此答案要么为 $0$,要么为 $1$。
```cpp
const int N = 1e3 + 7;
int n, a[N], b[N];
char s[N];
int main() {
rds(s, n);
vi ans;
for (int i = 1; i <= n; i++)
a[i] = a[i-1] + (s[i] == '(');
for (int i = n; i; i--)
b[i] = b[i+1] + (s[i] == ')');
for (int i = 0; i <= n; i++)
if (a[i] == b[i+1]) {
for (int j = 1; j <= i; j++)
if (s[j] == '(') ans.pb(j);
for (int j = i + 1; j <= n; j++)
if (s[j] == ')') ans.pb(j);
if (!ans.size()) {
print(0);
return 0;
}
print(1);
print(ans.size());
for (int x : ans) print(x, ' ');
return 0;
}
return 0;
}
```