牛客春招刷题训练营-2025.5.2题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小欧的括号嵌套

先构造嵌套层数为 的括号序列，最后用一层括号补齐长度到 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, r;
    cin >> n >> r;
    string s;
    for (int i = 0; i < r; i++)s += "(";
    for (int i = 0; i < r; i++)s += ")";
    while (s.length() < 2 * n)s += "()";
    cout << s;
    return 0;
}

中等题 不相邻取数

动态规划。
为不取第 个数的情况下，前 个数取数的最大值， 为取第 个数的情况下，前 个数取数的最大值。
取了，则 一定不能取。
。
不取，则 可取可不取，取其中最大值。
。
最后答案为 \max(dp_{n,1},dp_{n,0})。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<array<long long, 2>> dp(n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        dp[i][1] = dp[i - 1][0] + a[i];
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
    return 0;
}

困难题 小红的树

从 号节点开始深度优先搜索。
搜索过程中，如果当前节点有子节点，先递归搜索该子节点，然后当前节点子树的红色节点个数加上该子节点子树的红色节点个数。
这样就能求出所有节点的子树红色节点个数，询问时直接查表。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> red(n + 1);
    vector<vector<int>> ver(n + 1);
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        ver[x].push_back(i);
    }
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        red[i] = (s[i - 1] == 'R' ? 1 : 0);
    }
    vector<int> subtreered(n + 1);
    auto dfs = [&](auto&& self, int i)->void {
        if (red[i])
            subtreered[i]++;
        for (auto it : ver[i]) {
            self(self, it);
            subtreered[i] += subtreered[it];
        }
    };
    dfs(dfs, 1);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << subtreered[x] << '\n';
    }
    return 0;
}