Bracket Subsequence

wjh15101051's space

卧薪尝胆，厚积薄发。

Bracket Subsequence

Date: Sat Oct 20 21:43:08 CST 2018

In Category: NoCategory

Description：

给一个合法括号序列，求一个长为 $k$ 的合法子括号序列。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

括号序列的一个重要思路是用栈。

这题按照题解的神奇思路只要把每次弹栈的两个括号的位置打标记，够 $k$ 个了就退出，最后输出所有有标记的位置即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

inline char getc()

{

	register char c = getchar();

	while(c != '(' && c != ')')c = getchar();

	return c;

}

#define MAXN 200010

char c[MAXN];

int s[MAXN],top = 0;

bool tag[MAXN];

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)c[i] = getc();

	int cnt = 0;

	for(int i = 1;i <= n;++i)

	{

		if(c[i] == '(')

		{

			s[++top] = i;

		}

		else

		{

			tag[s[top--]] = true;

			tag[i] = true;

			k -= 2;

			if(k == 0)break;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		if(tag[i])putchar(c[i]);

	}

	return 0;

}

In tag: 数据结构-栈

wjh15101051