HDU5831

Rikka with Parenthesis II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 857    Accepted Submission(s): 442

Problem Description
As
we know, Rikka is poor at math. Yuta is worrying about this situation,
so he gives Rikka some math tasks to practice. There is one of them:

Correct parentheses sequences can be defined recursively as follows:
1.The empty string "" is a correct sequence.
2.If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
3.If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

Now Yuta has a parentheses sequence S, and he wants Rikka to choose two different position i,j and swap Si,Sj.

Rikka
likes correct parentheses sequence. So she wants to know if she can
change S to a correct parentheses sequence after this operation.

It is too difficult for Rikka. Can you help her?

 
Input
The
first line contains a number t(1<=t<=1000), the number of the
testcases. And there are no more then 10 testcases with n>100

For
each testcase, the first line contains an integers
n(1<=n<=100000), the length of S. And the second line contains a
string of length S which only contains ‘(’ and ‘)’.

 
Output
For each testcase, print "Yes" or "No" in a line.
 
Sample Input
3
4
())(
4
()()
6
)))(((
 
Sample Output
Yes
Yes
No
Hint

For the second sample input, Rikka can choose (1,3) or (2,4) to swap. But do nothing is not allowed.

 
Author
学军中学
 
Source
 /*
找出几个特殊情况,剩下的就好办了,))((也是可以的,()不可以。从左向右,(,a++,如果是)并且a==0,b++;a!=0,a--;
*/
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
int t,n;
string s;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cin>>s;
int a=,b=;
int k=s.size();
if(n%==)
{
printf("No\n");
continue;
}
for(int i=;i<n;i++)
{
if(s[i]=='(') a++;
else if(s[i]==')')
{
if(a==)
b++;
else a--;
}
}
if(a==&&b==)
printf("Yes\n");
else if(a==&&b==&&n!=)
printf("Yes\n");
else if(a==&&b==)
printf("Yes\n");
else printf("No\n");
}
return ;
}
上一篇:SQL Server 为索引启动硬件加速(分区)的 2 方法


下一篇:Xshell和VirtualBox虚机CentOS7的连接