BUPT2017 wintertraining(16) #4 G

HDU - 5831

题意

给定括号序列，问能否交换一对括号使得括号合法。

题解

注意()是No的情况。

任意时刻)不能比(超过2个以上。

最后)和(的差距要在两个以内，且n必须是偶数。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

char s[100006];

int t;

int main() {

	scanf("%d",&t);

	while(t--){

		scanf("%*d%s",s);

		if(s[0]=='('&&s[1]==')'&&!s[2]){puts("No");continue;}

		int i,ok=1,a=0;

		for(i=0;s[i];i++){

			if(s[i]==')')a--;else a++;

			if(a<-2){

				ok=0;break;

			}

		}

		if(i%2==0&&ok&&(a>-2||a<2))puts("Yes");else puts("No");

	}

	return 0;

}