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

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

简单题 求最大连续bit数

位运算。
遇到 则当前连续段的长度 ，否则当前连续段的长度清零。
输出连续段的最大值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = 0, tmp = 0;
    for (int i = 0; i < 30; i++) {
        if (((n >> i) & 1) != 0) {
            tmp++;
            ans = max(ans, tmp);
        } else tmp = 0;
    }
    cout << ans << '\n';
    return 0;
}

中等题 小红的排列构造

当 时，构造 ，则会在第一个 出现的地方漏掉一个 ，记为 。
当 时，如果 ，则把前面漏掉的数补上，，否则正常构造 。
最后一个位置一定是 ，否则就无法构造，输出 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n);
    int l = 1, r = 2;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            a[i] = i + 2;
        } else {
            a[i] = l;
            l = i + 2;
        }
    }
    for (int i = 0; i < n; i++)
        if (a[i] > n) {
            cout << -1;
            return 0;
        }
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}

困难题 [NOIP2001]装箱问题

动态规划。
表示是否能装到体积 。
初始化。
装到体积为 的物品时，遍历一遍 数组，如果 为 则令 。
最后找出 中最大的 。 使用 bitset 可直接用 << 和 | 运算符实现状态转移。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int V, n;
    cin >> V >> n;
    bitset<20001> dp;
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        dp |= (dp << v);
    }
    for (int i = V; i >= 0; i--) {
        if (dp[i]) {
            cout << V - i << '\n';
            return 0;
        }
    }
    return 0;
}