Codeforces 1097C. Yuhao and a Parenthesis——————思维

偏执的太偏执、 2022-03-30 15:54 166阅读 0赞

# [C. Yuhao and a Parenthesis][] #

One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it’s possible to obtain a correct arithmetic expression by inserting characters “+” and “1” into this sequence. For example, the sequences “(())()”, “()” and “(()(()))” are correct, while the bracket sequences “)(”, “(()” and “(()))(” are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?

**Input**  
The first line contains one integer n (1≤n≤105) — the number of bracket sequences.

Each of the following n lines contains one bracket sequence — a non-empty string which consists only of characters “(” and “)”.

The sum of lengths of all bracket sequences in the input is at most 5⋅105.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn’t matter.

**Output**  
Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.

**Examples**  
input  
7  
)())  
)  
((  
((  
(  
)  
)  
output  
2  
input  
4  
(  
((  
(((  
(())  
outputCopy  
0  
input  
2  
(())  
()  
output  
1  
Note  
In the first example, it’s optimal to construct two pairs:  " ( ( ) ( ) ) " "(( \\qquad )())" "(()())" and  " ( ) " "( \\qquad )" "()".

--------------------

Hello 2019的C题，一道字符串的思维题，  
会这道题的前提需要会括号匹配问题，不过这一道题在括号匹配的基础上复杂了一些

题意就是给你n个仅包括“(” 和 ")"的字符串，让你从这些字符串中进行两两组合，使得两个串组成一个串之后，所组成的括号序列是**correct**的，要求组成尽量多的correct括号序列串  
比如第一个样例 " ( ( " 和 " ) ( ) ) " "(( " 和 ")())" "(("和")())"组成一串  " ( " 和 " ) " "( "和 " )" "("和")"组成一串.所以结果是2

我们来分析一下:

对于任意一个括号序列，我们都可以让它进行自身匹配之后形成一个新的序列  
比如 “)())”，在进行朴素的括号匹配之后形成的是 “))”，  
显然我们可以得出这样的结论，对于任意一个括号序列，在进行任意的括号匹配之后，该序列会称为以下几种序列：

*  " " ，第一种，空序列
 *  " (((… "，第二种，包含若干个左括号的序列
 *  " )))… " ，第三种，包含若干个右括号的序列
 *  " ))…((… " ，第四种，包含若干个右括号，和若干个左括号的序列

显然：  
空序列和空序列组合的结果是正确的  
x 个左括号和 x 个右括号组合的结果是正确的，即第二种可以和第三种进行组合（如果个数相同）  
第四种不符合要求，因为它和上边的任意一种都不能形成正确的组合

综上。

code：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 5e5+7;
    string s[MAXN];
    ll l[MAXN],r[MAXN];
    ll L[MAXN],R[MAXN];
    int main()
    {
        
    	int n;
    	ll cnt = 0;
    	ll ans = 0;
    	cin>>n;
    	for(int i=0;i<n;++i)
    	{
        
    		cin>>s[i];
    		stack<char> sta;
    		for(int j=0;j<s[i].size();++j)
    		{
        
    				if(s[i][j]=='(')
    				{
        
    					sta.push('(');
    					l[i]++;
    				}
    				else 
    				{
        
    					if(sta.size())
    					{
        
    						sta.pop();
    						l[i]--;
    					}
    					else
    					{
        
    						r[i]++;
    					}
    				}	
    		} 
    	}
    	for(int i=0;i<n;++i)
    		if((l[i]&&!r[i])||(!l[i]&&r[i]))
    		{
        
    			s[cnt] = s[i];
    			l[cnt] = l[i];
    			r[cnt] = r[i];
    			cnt++;
    		}
    		else if((!l[i])&&(!r[i]))
    			ans++;
    	ans /= 2;
    	memset(L,0,sizeof(L));
    	memset(R,0,sizeof(R));
    	for(int i=0;i<cnt;++i)
    		if(l[i])	L[l[i]]++;
    		else		R[r[i]]++;
    	for(int i=0;i<MAXN;++i)
    		ans += min(L[i],R[i]);
    	cout<<ans<<endl;			
    	return 0; 
    }

[C. Yuhao and a Parenthesis]: https://codeforces.com/problemset/problem/1097/C