CF1896F Bracket Xoring

樱雪喵 · 2023-10-06 23:25:18 · 题解

Description

给定一个长度为 2n 的 \texttt{01} 串 s。一次操作定义为：

• 选择一个长度为 2n 的合法括号串（所有括号均匹配）；
• 对于每个左括号，设它的位置为 l，与它匹配的右括号位置为 r，将 s 的 [l,r] 这个区间取反（\texttt{0} 变成 \texttt{1}，\texttt{1} 变成 \texttt{0}）。

请构造方案在 10 次操作内将 s 的所有位置变为 \texttt{0}，并输出方案。

多组数据，T\le 10^3，\sum n\le 2\times 10^5。

Solution

先找一些比较容易直接看出来的性质。

• 每次操作都一定会改变 s_1 和 s_{2n}，故 s_1\neq s_{2n} 无解；
• 每次操作都会取反偶数个位置，故 s 中有奇数个 1 无解。

注意到只要这个字符串满足 \forall i\bmod 2=0,s_i=s_{i+1}（不含首尾），就可以用一次操作让整个字符串变成一样的。

先假设这里的 s_1=\texttt{1}，如果不是可以先做一次 \texttt{()()\dots()} 操作将整个串取反。

具体地，从开头开始令每两个相邻的 \texttt{1} 配成一对括号，显然这些括号位置的取反次数都是 1；每两个相邻的 \texttt{1} 之间一定有偶数个 \texttt{0}，我们把它们两两配对成 \texttt{()()\dots} 的形式，那么它们因为包含在一组 \texttt{1} 形成的括号内，均不会被取反。
例如 s=\texttt{1000011001}，则构造操作 \texttt{(()())(())}。

所以我们如果能构造一些前置操作使字符串满足这个条件就做完了。

考虑对于一个任意的串，怎么让 s_i 和 s_{i+1} 相等：

• 若本身就 s_i=s_{i+1}，在这里放一对 \texttt{()}，那么这两位的取反状态一定是一样的；
• 否则要么放两个左括号要么放两个右括号，我们根据前面未匹配的括号数判断：如果有未匹配的括号（显然这不会是一个奇数），在这里放 \texttt{))}，否则放 \texttt{((}。

第二种情况一定出现偶数次（否则不满足有偶数个 1），所以这样构造出的括号串一定是匹配的。

综上，我们至多使用三步操作使 s 全为 0。

写代码的时候精神状态堪忧，可能和上面讲的没什么关系。（upd: 重写了。）

const int N=4e5+5;
int T,n,a[N],b[N],c[N];
char s[N];
int main()
{
    T=read();
    while(T--)
    {
        n=read()<<1; scanf("%s",s+1);
        for(int i=1;i<=n;i++) a[i]=s[i]-'0';
        int cnt=0; for(int i=1;i<=n;i++) cnt+=a[i];
        if(a[1]!=a[n]||(cnt&1)) {printf("-1\n");continue;}
        if(a[1])
        {
            printf("3\n"); 
            for(int i=1;i<=n;i++) a[i]^=1,printf(i&1?"(":")"); printf("\n");
        }
        else printf("2\n");
        int sum=0; a[1]^=1,a[n]^=1;
        printf("(");
        for(int i=2;i<n;i+=2) 
        {
            if(a[i]==a[i+1]) printf("()");
            else if(!sum) printf("(("),a[i+1]^=1,sum^=1;
            else printf("))"),a[i]^=1,sum^=1;
        }
        printf(")\n(");
        for(int i=2;i<n;i+=2) printf(a[i]?")(":"()");
        printf(")\n");
    }
    return 0;
}