2019 括号树 · 方案一逐点重算

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1460 字

n 个点的树，1 号为根，每点挂 ( 或 )

2019
树

正文

// CSP-S 2019 复赛 T2 · 括号树（方案一：逐点重算，链与小树部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2019B
// 题意：n 个点的树，1 号为根，每点挂 ( 或 )。s_i = 根到 i 的括号串，
//       a_i = s_i 中"合法括号串"的出现个数。对每个 i 输出
//       (1·a_1) XOR (2·a_2) XOR ... XOR (i·a_i)。
// 思路（暴力基准）：
//   对每个点 i：沿父亲指针把根到 i 的字符收进串（收集后反转），
//   然后用栈扫一遍统计合法对数：
//   - '(' 入栈；')' 若栈非空则弹栈并 count++（一对合法括号）；
//   - a_i = count，边算边累计前缀异或和。
//   每个 i 独立重算为 O(n)，总 O(n^2)：n ≤ 2000 的部分分稳过，
//   逻辑直白，适合理解题意与给满分做法做对拍。
// 复杂度：O(n^2)。
// 易错点：
//   1. 前缀异或和边扫边累计，别漏掉 i = 1；
//   2. 收集的串是从 i 往根，要 reverse；
//   3. i * a_i 可达 1.25e11，用 unsigned long long 存异或和。
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int par[2200];
char ch[2200];

long long countPairs(const string& s) {
    long long cnt = 0;
    vector<char> st;
    for (char c : s) {
        if (c == '(') st.push_back(c);
        else if (!st.empty()) { st.pop_back(); cnt++; }
    }
    return cnt;
}

int main() {
    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout);
    int n;
    scanf("%d", &n);
    scanf("%s", ch + 1);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    unsigned long long sum = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        for (int u = i; u != 0; u = par[u]) s.push_back(ch[u]);
        reverse(s.begin(), s.end());
        long long a = countPairs(s);
        sum ^= (unsigned long long)i * a;
        printf("%llu\n", sum);
    }
    return 0;
}

2019 括号树 · 方案一 逐点重算

正文

CSP-S 标程 · 复赛真题的其它内容

2019 括号树 · 方案一逐点重算