【HDU5831】Rikka with Parenthesis II（括号）

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;
}
           

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆