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

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

简单题 小红的校招笔试

给所有人的成绩降序排序后，即回答小红的成绩是否 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    int x = a[1];
    sort(a.begin() + 1, a.end(), greater<>());
    if (x >= a[n / 2])cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

中等题 小红的区间查询

数据范围较小，所以可以直接暴力统计……
对每一次操作 ，直接修改。
对每一次操作 ，直接暴力统计 上 的个数。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, x;
            cin >> i >> x;
            a[i] = x;
        } else {
            int i, x;
            cin >> i >> x;
            int ans = 0;
            for (int j = 1; j <= i; j++)
                if (a[j] == x)
                    ans++;
            cout << ans << '\n';
        }
    }
    return 0;
}

困难题 最长回文子序列

求最长回文子序列，可将 倒置成 ，求 和 的最长公共子序列。
最长公共子序列解法见此 最长公共子序列

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    string t = " "s + string(s.rbegin(), s.rend());
    s = " "s + s;
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i] == t[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[n][n] << '\n';
    return 0;
}