分析
这个数据规模显然是 $O(T \times N)$ 的。普通的括号匹配用栈，那这个也用栈。对每一个字符串分别维护一个栈。
如果按照这种方式放置后，两个括号序列在匹配过程中都不会出现 右括号找不到对应左括号 的情况，那么称这种放置方式合法。
从前往后扫：
若第 i 位的两个字符相同
若当前放置方式能够保证两个序列仍然满足括号匹配的必要条件，则按该方式放置；否则答案不存在。
若第 i 位的两个字符不同
- 若两种放置方案均合法，其中一定有一个是右括号。需要贪心一下：将右括号放入未匹配左括号数量较多的序列中，从而优先消去更多待匹配的左括号。
- 若两种放置方案均不合法，则不存在可行解。
- 若仅一种放置方案合法，则只能采用该方案。
扫完后判断栈是否全空。全空就是 YES，不空就是 NO。
做到这可以发现其实根本不需要用栈，只需要记录没有匹配的左括号数量即可。
参考代码
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
89
90
91
92
93
94
95
| #include <iostream>
#include <stack>
using namespace std;
int f(char c) {
if (c == '(') return -1;
if (c == ')') return 1;
return 0;
}
int n;
string s1, s2;
stack<int> st1, st2;
bool ch(int a, int b) {
bool o1 = 0, o2 = 0;
if (a == -1 || (a == 1 && !st1.empty() && st1.top() == -1)) {
o1 = 1;
}
if (b == -1 || (b == 1 && !st2.empty() && st2.top() == -1)) {
o2 = 1;
}
return o1 && o2;
}
bool solve() {
cin >> n;
cin >> s1 >> s2;
for (int i = 0; i < n; i++) {
int a = f(s1[i]), b = f(s2[i]);
if (a == b) {
if (ch(a, b)) {
if (a == -1)
st1.push(a);
else
st1.pop();
if (b == -1)
st2.push(b);
else
st2.pop();
} else {
return 0;
}
} else {
if (!(ch(a, b) || ch(b, a))) {
return 0;
} else if (ch(a, b) && ch(b, a)) {
if (st1.size() < st2.size()) {
st1.push(-1);
st2.pop();
} else {
st2.push(-1);
st1.pop();
}
} else if (ch(a, b)) {
if (a == -1)
st1.push(-1);
else
st1.pop();
if (b == -1)
st2.push(-1);
else
st2.pop();
} else {
if (b == -1)
st1.push(-1);
else
st1.pop();
if (a == -1)
st2.push(-1);
else
st2.pop();
}
}
}
if (st1.empty() && st2.empty())
return 1;
else
return 0;
}
void clear() {
n = 0;
s1 = "";
s2 = "";
while (!st1.empty()) st1.pop();
while (!st2.empty()) st2.pop();
}
int main() {
int t;
cin >> t;
while (t--) {
if (solve()) {
cout << "YES\n";
} else {
cout << "NO\n";
}
clear();
}
}
|