P8235 [AGM 2022 资格赛] 括号 题解

· · 题解

解题思路

其实想清楚如何构造之后就很简单了。

我们考虑连续的单个括号（比如()()）和嵌套的括号（比如(())）这样的两种括号序列，假设他们在一条链上，连续的有 3 个合法括号序列，但是嵌套的只有 2 个，所以我们要把这棵树上所有路径都尽量设计成连续的单个括号这种形式。

一号点的括号已经给出来了。想要构造连续的括号，显然可以对于每一个节点，让它成为和它父节点相反的括号。

这个过程用搜索实现就好了。

看到题解区好像都是用 dfs 写的，因此我选择用 bfs

AC Code

#include <bits/stdc++.h>
using namespace std;
struct Edge{int to, next;}e[200001];
int n, head[100001], tot, ans[100001];
bool vis[100001];

inline void addedge(int u, int v){
    e[++tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

int main(){
    scanf("%d", &n);
    int u, v, tmp;
    for (int i=1; i<n; i++){
        scanf("%d%d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    queue<int> q; q.push(1);
    vis[1] = 1; ans[1] = 0; 
    while (!q.empty()){
        u = q.front(); q.pop();
        for (int i=head[u]; i; i=e[i].next) if (!vis[e[i].to]){
            v = e[i].to;
            ans[v] = ans[u] ^ 1;
            q.push(v); vis[v] = 1;
        }
    }
    for (int i=1; i<=n; i++) printf("%c", ans[i] ? ')' : '(');
    return 0;
}

貌似跑的还挺快