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

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

简单题 小欧的奇数

挑出 个奇数，或者 个偶数 + 个奇数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ji = 0, ou = 0;
    while (n--) {
        int x;
        cin >> x;
        if (x % 2)ji++;
        else ou++;
    }
    if (ji >= 3)cout << "YES";
    else if (ji && ou >= 2)cout << "YES";
    else cout << "NO";
    return 0;
}

中等题 拦截导弹

第一个问题，是最长不上升子序列问题，用 dp 求解，时间复杂度 。
第二个问题，最多只会有 个拦截系统，可以假设 个拦截系统全部用上，且这 个系统发射的上一发导弹的高度为无穷大（设为 ），每来一发导弹贪心地用拦截高度 且上一发导弹高度最小的拦截系统去拦截导弹，最后统计有几个系统的高度不为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n), dp(n, 1);
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[i] <= a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
    vector<int> b(n, 1e9);
    for (int i = 0; i < n; i++) {
        int minn = 1e9;
        for (int j = 0; j < n; j++) {
            if (b[j] >= a[i]) {
                minn = min(minn, b[j]);
            }
        }
        for (int j = 0; j < n; j++) {
            if (b[j] == minn) {
                b[j] = a[i];
                break;
            }
        }
    }
    int ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (b[i] != 1e9) {
            ans2++;
        }
    }
    cout << ans2 << '\n';
    return 0;
}

困难题 红和蓝

首先如果 为奇数，一定无解。
取任一节点为根。
记 为以 为根的子树的大小（或点数）。
从根节点开始dfs，dfs过程中，如果遇到该节点 个子树的大小为奇数，则无解。
否则，如果有 个子树的大小为奇数，将该子树的根染成其父节点一样的颜色，其余子树的根全部染成与父节点相异的颜色。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<vector<int>> ver(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        ver[u].push_back(v);
        ver[v].push_back(u);
    }
    vector<int> siz(n + 1);
    bool ok = true;
    auto dfs1 = [&](auto&& self, int i, int fa)->void {
        siz[i] = 1;
        int cnt = 0;
        for (auto it : ver[i]) {
            if (it != fa) {
                self(self, it, i);
                siz[i] += siz[it];
                if (siz[it] % 2 == 1)cnt++;
            }
        }
        if (cnt > 1)ok = false;
    };
    if (n % 2 == 1)ok = false;
    dfs1(dfs1, 1, 0);
    if (!ok) {
        cout << "-1\n";
        return 0;
    }
    vector<int> color(n + 1);
    auto dfs2 = [&](auto&& self, int i, int fa, int c)->void {
        color[i] = c;
        for (auto it : ver[i]) {
            if (it != fa) {
                if (siz[it] % 2 == 0)self(self, it, i, c ^ 1);
                else self(self, it, i, c);
            }
        }
    };
    dfs2(dfs2, 1, 0, 0);
    for (int i = 1; i <= n; i++)
        cout << (color[i] ? 'R' : 'B');
    cout << '\n';
    return 0;
}