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

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

简单题 小红的顺子

设 为当前顺子长度，其初值为 ，如果 则将 增加 ，否则将 设成 。
同时用 记录整个过程的 的最大值。
输出 即为答案。

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

中等题 小红的字符生成

个 可变成 个 ， 个 可变成 个 ……发现为 的幂次关系。
即求 的二进制表示中所有 的位置。
当 的二进制表示第 位是 ，则输出 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 10; i >= 0; i--) {
        if (n >= (1 << i)) {
            n -= (1 << i);
            cout << char('a' + i);
        }
    }
    return 0;
}

困难题 最少的完全平方数

完全背包问题，相当于体积分别为 且数量无限多的物品装满体积为 的背包需要最少几个物品。
因存在体积为 的物品，所以背包一定能装满。
设 为装满体积为 的背包需要最少几个物品。
，否则 。
转移时，设 为完全平方数的底数，。
答案为 。
时间复杂度 ，本做法将常数直接设成了 ，更优化常数的做法为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> dp(n + 1, 1e9);
    dp[0] = 0;
    for (int i = 1; i <= 100; i++)
        for (int j = i * i; j <= n; j++)
            dp[j] = min(dp[j], dp[j - i * i] + 1);
    cout << dp[n] << '\n';
    return 0;
}