思维

📝 核心思路 合法括号序列: ‘ ( ’ : 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; }