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

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

简单题 查找输入整数二进制中1的个数

使用gcc内置 __builtin_popcount() 函数即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    cout << __builtin_popcount(n) << endl << __builtin_popcount(m) << endl;
    return 0;
}

中等题 宝石手串

宝石最多只有 种，可以枚举每一种宝石。
对于每种宝石，枚举两个相邻的这种宝石，设其下标分别为 ，则摘掉这两个宝石之间的所有宝石所需的操作次数为 。
如果没有一种属性有 个宝石则无解。

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9;
void solve() {
    vector<vector<int>> a(26);
    int ans = INF;
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
        a[s[i] - 'a'].push_back(i);
    for (int i = 0; i < 26; i++) {
        int m = a[i].size();
        if (m > 1)
            for (int j = 0; j < m; j++)
                ans = min(ans, min(abs(a[i][j] - a[i][(j + 1) % m]),
                                   n - abs(a[i][j] - a[i][(j + 1) % m])) - 1);
    }
    if (ans == INF)cout << -1 << '\n';
    else cout << ans << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}

困难题 最长上升子序列(一)

动态规划。
设 为截止到下标 的最长上升子序列长度。
转移方程为 。
最后输出 。

#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[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}