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
#include<cstdio> #include<iostream> #include<cstring> char a[100010]; using namespace std; int main(void) { int T,n,i,tl,tr; cin>>T; while(T--){ cin>>n; memset(a,0,sizeof(a)); scanf("%s",a); if(n%2==1)//如果括号的个数是奇数直接NO cout<<"No"<<endl; else { int s=strlen(a); tl=0;tr=0; for(i=0;i<s;i++) { if(a[i]=='(') tl++; else tr++; } if(tl!=tr) cout<<"No"<<endl;//如果左括号数不等于右括号数直接NO else { if(n==2)//如果只有两个括号就分别判断一下 { if(strcmp(a,"()")==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } else { tl=0; tr=0; for(i=0;i<s;i++) { if(a[i]=='(') tl++; else tr++; if(tr>tl+2)//如果当后括号-前括号>2，输出NO break; } if(i==s) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } } } return 0; } //因为交换一次的话其实是改对两个后括号，如果有两个以上的单个后括号，那么改了也没用
