题解 | # Bracket Coloring #

Bracket Coloring

https://ac.nowcoder.com/acm/contest/127703/F

$[思维+并查集]$

没做过类似的题目，将括号想象成节点，然后转化为二分图的形式

就是将每一对括号想象成一个节点：

根据条件一：一对括号的染色情况必须相同，每一对匹配的括号，是一个颜色绑定的整体。可以直接把一对括号抽象成一个节点，节点的颜色就是这对括号的颜色，不用再单独考虑每个括号

根据条件二：相邻位置的括号字符相同，其颜色必须不同，假设相邻的两个相同字符，分别属于节点 u 和节点 v。因为这两个括号的颜色必须不同，而它们的颜色就是所属节点的颜色，所以节点 u 和节点 v 的颜色必须不同

那么问题转化为一个无向图二染色问题：

现在这里有若干个节点（对应每一对匹配的括号）

两个节点之间连一条边，当且仅当：存在相邻的两个相同字符，分别属于这两个节点

给每个节点染红 / 蓝，要求有边相连的节点颜色必须不同

求有多少种合法的染色方案？

答案就是 $2^{连通分量个数}$ ：

结论一：这个图一定是二分图，绝对有合法染色方案，不会出现答案为 0 的情况

合法括号序列的嵌套以及并列结构，决定了我们构建的图是无环的（森林），而无环图一定是二分图，不会出现奇环导致的染色矛盾，所以一定能染成功

结论二：每个连通分量只有 2 种染色方案

对于二分图的二染色，一旦你选定了连通分量里任意一个节点的颜色（红 / 蓝），整个连通分量里所有节点的颜色就被唯一确定了（相邻节点必须不同）

这段代码是给每对括号进行标号，用vector模拟栈

vector<int> pid(n + 10), sta;
int idx = 0;
for(int i = 1; i <= n; i ++){
    if(s[i] == '(') sta.push_back(i);
    else{
        int last = sta.back();
        pid[last] = pid[i] = ++ idx;
        sta.pop_back();
    }
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 200010;
const int mod = 998244353;

int p[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x]; 
}

int ksm(int a, int b, int p){
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum;
}

void solve(){
    int n; cin >> n;
    vector<char> s(n + 10);
    for(int i = 1; i <= n; i ++) cin >> s[i];
    vector<int> pid(n + 10), sta;
    int idx = 0;
    for(int i = 1; i <= n; i ++){
        if(s[i] == '(') sta.push_back(i);
        else{
            int last = sta.back();
            pid[last] = pid[i] = ++ idx;
            sta.pop_back();
        }
    }

    for(int i = 1; i <= idx; i ++) p[i] = i;
    for(int i = 1; i <= n - 1; i ++){
        if(s[i] == s[i + 1]){
            int u = pid[i], v = pid[i + 1];
            int fu = find(u), fv = find(v);
            if(fu != fv) p[fu] = fv;
        }
    }

    int cnt = 0;
    for(int i = 1; i <= idx; i ++) cnt += (p[i] == i);
    cout << ksm(2, cnt, mod) << endl;
    return ;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}