CF2223A Zhily and Bracket Swapping

思路

首先一个不合法的括号序列有两种情况：

  • 两种括号数量不相等。
  • 存在某个前缀中的后括号数量大于前括号的数量。

又因为两个字符串的括号不可以跨位交换，所以我们枚举 $i\in [0,n)$，对于每个 $i$ 维护四个值 $sw_1,sw_2,v_1,v_2$ 分别代表序列 $1$ 可以往序列 $2$ 交换过去的前括号数量，序列 $2$ 可以往序列 $1$ 交换过去的前括号数量，此时序列 $1$ 中前括号比后括号多多少个，此时序列 $2$ 中前括号比后括号多多少个。
首先特判若两者中总的两种括号数量不相等，则不成立。
然后考虑如何维护上面的四个值以及它们分别有什么用。
首先维护 $sw1,sw2$，根据定义可得：

1
2
if(a2[i]==1&&a1[i]==-1)sw1++;
if(a1[i]==1&&a2[i]==-1)sw2++;

若在某个 $i$，$v1,v2$ 中有一个小于 $0$ 且无法“挽回”，则不存在合法构造。
“挽回”是什么意思呢，就是通过将前面某处可交换的交换使得 $v1,v2$ 中的一个变多，另一个变少。
然后因为每一处 $i$ 前一位时的 $v1,v2$ 都 $\ge 0$，所以可交换的位一定是合法的，交换后也不会导致 $v1,v2$ 在前面的某一处 $<0$。
每一位上 $v1,v2$ 最多变化 $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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
	inline void read(T &x,Args&...args){
		read(x);
		read(args...);
	}
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47;
int T,n,a1[N],a2[N];
string s1,s2;
signed main(){
	read(T);
	while(T--){
		read(n);
		cin>>s1>>s2;
		int cnt=0;
		fep(i,0,n){
			if(s1[i]=='(')a1[i+1]=1;
			else a1[i+1]=-1,cnt++;
			if(s2[i]=='(')a2[i+1]=1;
			else a2[i+1]=-1,cnt++;
		}
		if(cnt!=n){
			puts("No");
			continue;
		}
		int sw1=0,sw2=0;
		int v1=0,v2=0,flg=1; 
		rep(i,1,n){
			if(a2[i]==1&&a1[i]==-1)sw1++;
			if(a1[i]==1&&a2[i]==-1)sw2++;
			v1+=a1[i],v2+=a2[i];
			if(v1<0&&v2<0){
				flg=0;
				break;
			}
			if(v1<0&&v2>0){
				if(sw1>0){
					sw1--;
					v2-=2;
					v1+=2;
				}
				else{
					flg=0;
					break;
				}
			} 
			if(v2<0&&v1>0){
				if(sw2>0){
					sw2--;
					v1-=2;
					v2+=2;
				}
				else{
					flg=0;
					break;
				}
			} 
			if(v1<0||v2<0){
				flg=0;
				break;
			}
		}
		if(flg)puts("Yes");
		else puts("No");
	}
}