📝 核心思路

合法括号序列: ‘ ( ’ : 1  ‘ ) ’ : -1
在1,3,5奇数位置,前缀和要为奇数且大于0
在2,4,6偶数位置,前缀和要为偶数且大于等于0
且在末尾前缀和为0

由上述规律考虑:
我们考虑a和b的总前缀和
则奇数位置 前缀和为偶数 且大于等于2
偶数位置 前缀和为偶数 且大于等于0
且到末尾 要为0
考虑交换:如果当前位置不同,则让前缀和小的加上1,大的减去1

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    int n;
    cin>>n;
    string a,b;
    cin>>a;
    cin>>b;
    a=" "+a;
    b=" "+b;
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=(a[i]=='(')?1:-1;
        sum+=(b[i]=='(')?1:-1;
        if( ( i&1 && sum<2 ) || ( !(i&1) && sum<0 ) ){
            cout<<"NO"<<"\n";
            return;
        }
    }
    if(sum!=0) cout<<"NO\n";
    else cout<<"YES\n";
}   

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ttt=1;
    cin>>ttt;
    while(ttt--){
        solve();
    }   
    //solve();
    return 0;
}