Codeforces.1305B Kuroni and Simple Strings[模拟]

题面

Now that Kuroni has reached 10 years old, he is a big boy and doesn't like arrays of integers as presents anymore. This year he wants a Bracket sequence as a Birthday present. More specifically, he wants a bracket sequence so complex that no matter how hard he tries, he will not be able to remove a simple subsequence!

We say that a string formed by nn characters '(' or ')' is simple if its length nn is even and positive, its first 2 / n characters are '(', and its last2 / n characters are ')'. For example, the strings () and (()) are simple, while the strings )( and ()() are not simple.

Kuroni will be given a string formed by characters '(' and ')' (the given string is not necessarily simple). An operation consists of choosing a subsequence of the characters of the string that forms a simple string and removing all the characters of this subsequence from the string. Note that this subsequence doesn't have to be continuous. For example, he can apply the operation to the string ')()(()))', to choose a subsequence of bold characters, as it forms a simple string '(())', delete these bold characters from the string and to get '))()'.

Kuroni has to perform the minimum possible number of operations on the string, in such a way that no more operations can be performed on the remaining string. The resulting string does not have to be empty.

Since the given string is too large, Kuroni is unable to figure out how to minimize the number of operations. Can you help him do it instead?

A sequence of characters aa is a subsequence of a string bb if aa can be obtained from bb by deletion of several (possibly, zero or all) characters.

题意

给定由'('、')'组成的字符串，删去所有左右匹配的括号并输出删去的括号的次数及位置

分析

对于字符串"（（））"，
第一个位置的"("可以和第三个位置的")"配对删去，
也可以和第四个位置的")"配对删去，所以删去的顺序与答案无关
那么考虑设两个指针分别指向第一个位置和最后一个位置
逐个的配对并计入答案即可

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read() {
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
	return x * f;
}

int main() {
	char s[1001];
	scanf("%s",s + 1);
	int cnt[1001];
	int sum = 0;
	int len = strlen(s + 1);
	int l = 1, r = len;
	while (l < r){
		while (s[l] == ')' && l < r) l++;//直指到"(";
		while (s[r] == '(' && l < r) r--;//直指到")";
		if (l >= r) break;
		cnt[++sum] = l++;
		cnt[++sum] = r--;//计入并开始下一位
	}
	if (!sum) puts("0");
	else{
		sort(cnt + 1, cnt + sum + 1);
		puts("1");
		printf("%d\n",sum);
		for (int i(1); i <= sum; i++) printf("%d ",cnt[i]);
		puts("");
	}
	return 0;
}