题解：CF1896F Bracket Xoring
WYZqaq
·
·
题解
本篇题解给出的做法是最多 5 次操作的。
首先，我们考虑无解情况，当且仅当 $a_1\ne a_{2n}$ 或字符串中的 $1$ 的个数为奇数，就不合法。
我们设 $cnt_{i}$ 表示 $1$ 到 $i$ 中有多少个 $1$，之后，我们考虑一个位置能被操作多少次，这个次数就是 $cnt_{i}-(i-cnt_{i}) + [ans_{i}=)]$ 次，$ans$ 表示操作的合法括号串。为什么，我们分类讨论一下，当这个位置为左括号时，当前位置会被自己和前面所有的没有被匹配上的贡献，之后我们考虑右括号，我们发现，如果直接按照左括号的公式算的话，会少 $1$，因为，当前的右括号还会额外贡献一次，之后我们发现这个东西操作的奇偶性，只和当前位置下标的奇偶性的当前放左右括号有关。
之后，我们考虑构造，首先，我们先将 $1$ 和 $2n$ 两个位置改成 $0$，这一步的话，我们使用 `()()()` 这样的括号串去改变，同时，中间所有值都会被反转，注意一下。
然后，我们考虑对于中间的点，我们假设我们能够实现 $i$ 和 $i+1$ 相邻两位反转的操作，这样的话，我们假设 $x$ 为是否对 $i$ 和 $i+1$ 进行一次这种操作，之后，我们发现，我们想要让每一个位置都变成 $0$，即 $x_{i}\operatorname{xor} a_{i} \operatorname{xor} x_{i-1} = 0$ 所以，我们让 $x$ 成为 $1$ 到 $i$ 的异或和就好了。
之后，我们考虑 $x$ 需要做操作的位置，奇偶位置分讨，我们先考虑偶数位置，我们先在开头和结尾加上 `(` 和 `)` 中间的部分，两位两位考虑，对于某一个偶数位置，如果需要操作，我们使用 `)(` 字符串，不然的话，我们使用 `()` 字符串，解释这个东西，我们发现，对于一个需要操作的位置来讲，它的 $cnt_{i}-1$，它的 $i-cnt_{i}$ 多了 $1$，这个东西变成了 `)` 所以说这个东西的操作次数少了 $1$。对于正常的来讲，发现每一个位置（不包括自己）前面的左括号数减右括号数恰好为 $1$ 再加上自己，恰好为 $2$。这样的话，我们就完成了对于偶数位置的操作，
奇数位置是一样的，在开头和结尾再加上一对 `()` 就行了。
讲的比较抽象，看代码吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
string ans[6];
int a[200005];
int biao[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
ans[1].clear();
ans[2].clear();
ans[3].clear();
ans[4].clear();
ans[5].clear();
int n;
cin>>n;
string s;
cin>>s;
s=' '+s;
int cnt=0;
for(int i=1;i<=2*n;i++){
a[i]=s[i]-'0';
}
for(int i=1;i<=2*n;i++){
if(a[i]==1){
cnt++;
}
}
if(cnt%2||(a[1]!=a[2*n])){
cout<<"-1\n";
continue;
}
int tot=0;
if(a[1]==1){
++tot;
for(int i=1;i<=2*n;i+=2){
ans[tot]=ans[tot]+'(';
ans[tot]=ans[tot]+')';
a[i]^=1;
a[i+1]^=1;
}
}
for(int i=2;i<2*n;i++){//这个东西和题解讲的写法不是很一样，但是都是对的
if(a[i]==1){
biao[i]=1;
a[i+1]^=1;
a[i]^=1;
}
}
int cnt2=0;
for(int i=2;i<2*n;i++){
if(i%2==0&&biao[i]){
cnt2++;
}
}
if(cnt2){
++tot;
ans[tot]='(';
for(int i=2;i<2*n;i+=2){
ans[tot]=ans[tot]+'(';
ans[tot]=ans[tot]+')';
}
ans[tot]=ans[tot]+')';
++tot;
ans[tot]=ans[tot]+'(';
for(int i=2;i<2*n;i+=2){
if(biao[i]){
ans[tot]=ans[tot]+')';
ans[tot]=ans[tot]+'(';
}
else{
ans[tot]=ans[tot]+'(';
ans[tot]=ans[tot]+')';
}
}
ans[tot]=ans[tot]+')';
}
cnt2=0;
for(int i=2;i<2*n;i++){
if((i%2)&&biao[i]){
cnt2++;
}
}
if(cnt2){
++tot;
ans[tot]="((";
for(int i=3;i<2*n-1;i+=2){
ans[tot]=ans[tot]+'(';
ans[tot]=ans[tot]+')';
}
ans[tot]=ans[tot]+')'+')';
++tot;
ans[tot]="((";
for(int i=3;i<2*n-1;i+=2){
if(biao[i]){
ans[tot]=ans[tot]+')';
ans[tot]=ans[tot]+'(';
}
else{
ans[tot]=ans[tot]+'(';
ans[tot]=ans[tot]+')';
}
}
ans[tot]=ans[tot]+')'+')';
}
cout<<tot<<"\n";
for(int i=1;i<=tot;i++){
cout<<ans[i]<<"\n";
}
for(int i=1;i<=n;i++){
biao[i]=0;
}
}
return 0;
}
```