给定一个括号序列，交换其中的两个括号 问是否能使得交换一次后的序列合法
贪心乱搞
首先一个括号序列左括号和右括号数量不相等，则不合法如果一个序列已经合法了，并且有两个及以上的左括号 那么交换这两个左括号，依旧合法，否则就是不合法的如果一个序列开始不合法，那么找到最左边使得序列不合法的右括号 以及最右边使得序列不合法的左括号，交换他们的位置， 再check一下是否合法 #pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <cctype> #include <map> #include <set> #include <queue> #include <bitset> #include <string> using namespace std; typedef pair<int,int> Pii; typedef long long LL; typedef unsigned long long ULL; typedef double DBL; typedef long double LDBL; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define SQR(a) ((a)*(a)) #define PCUT puts("\n----------") const int maxn=1e5+10; int N; char str[maxn]; bool check(char*,int); int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif int T; scanf("%d", &T); for(int ck=1; ck<=T; ck++) { bool ok=0; scanf("%d %s", &N, str); int lcnt=0,rcnt=0; for(int i=0; i<N; i++) { if(str[i]=='(') lcnt++; else rcnt++; } if(lcnt!=rcnt) puts("No"); else if(check(str,N)) { if(lcnt>=2) puts("Yes"); else puts("No"); } else { int sum=0, l, r; for(int i=0; i<N; i++) { if(str[i]=='(') sum++; else sum--; if(sum<0) {l=i; break;} } sum=0; for(int i=N-1; i>=0; i--) { if(str[i]==')') sum--; else sum++; if(sum>0) {r=i; break;} } swap(str[l], str[r]); if(check(str,N)) puts("Yes"); else puts("No"); } } return 0; } bool check(char str[], int len) { int sum=0; for(int i=0; i<len; i++) { if(str[i]=='(') sum++; else sum--; if(sum<0) return 0; } if(sum!=0) return 0; return 1; }