题解：CF1503A Balance the Bits
__Clannad__ · · 题解
原题
我们需要构造两个平衡的括号序列
-
如果
s_i = 1 ，则a_i = b_i 。 -
如果
s_i = 0 ，则a_i \ne b_i 。
思路
平衡的括号序列需要满足每个左括号 ( 都有一个对应的右括号 )。
-
对于
s_i = 1 的位置，则a_i 和b_i 必须相同。 -
对于
s_i = 0 的位置，则a_i 和b_i 必须不同。
显然，如果 1 的数量是奇数，则无法构造满足条件的序列，因为每个 1 需要成对出现。
容易想到一种构造方法：
-
将
s 中的1分成两半，前一半为(，后一半为)。 -
将
s 中的0交替分配给a 和b 。
具体细节看代码。
代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
// 统计 1 的数量
int count1 = 0;
for (char c : s) {
if (c == '1') {
count1++;
}
}
// 如果 1 的数量是奇数，无法构造
if (count1 % 2 != 0) {
cout << "NO\n";
return;
}
// 构造 a 和 b
string a(n, ' '), b(n, ' ');
int half1 = count1 / 2;
int flip = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
if (half1 > 0) {
a[i] = '(';
b[i] = '(';
half1--;
} else {
a[i] = ')';
b[i] = ')';
}
} else {
if (flip == 0) {
a[i] = '(';
b[i] = ')';
} else {
a[i] = ')';
b[i] = '(';
}
flip = 1 - flip;
}
}
// 检查 a 和 b 是否平衡
int balanceA = 0, balanceB = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == '(') {
balanceA++;
} else {
balanceA--;
}
if (b[i] == '(') {
balanceB++;
} else {
balanceB--;
}
if (balanceA < 0 || balanceB < 0) {
cout << "NO\n";
return;
}
}
if (balanceA != 0 || balanceB != 0) {
cout << "NO\n";
return;
}
cout << "YES\n";
cout << a << '\n';
cout << b << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}时间复杂度