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

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

简单题 小红的好数组

遍历 并检查 是否构成非降序，如果构成，则需要修改一个元素。
修改头尾不是最优的，因为修改头尾可能会使前后的元素和头尾构成了新的非降序子数组。
所以需要修改中间。
需要将 修改成 ，同时答案 。
时间复杂度 。

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

中等题 压缩二维码

首先将 行字符串拼成 行。
然后按长度为 的子串遍历字符串，记该子串为 。
中#号视为 ，否则视为 ，将 转为十进制数字输出。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    n = (1 << n);
    string s;
    for (int i = 0; i < n; i++) {
        string t;
        cin >> t;
        s += t;
    }
    for (int i = 0; i + 3 < n * n; i += 4) {
        string subs = s.substr(i, 4);
        int ans = 0;
        for (int j = 0; j < 4; j++) {
            if (subs[j] == '#')
                ans += (1 << (3 - j));
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

困难题 分割等和子集

嗯……又是01背包。
记数组总和为 。
本题即为求01背包中是否存在装的物品体积总和为 的方案。
如果 为奇数，无解。
否则设背包容量为 跑01背包，检查是否有体积为 的装配方案。
时间复杂度 ，可以通过。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    int sum = accumulate(a.begin(), a.end(), 0);
    if (sum % 2 == 1) {
        cout << "false\n";
    } else {
        vector<int> dp(sum + 1);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= a[i]; j--) {
                if (dp[j - a[i]]) {
                    dp[j] = 1;
                }
            }
        }
        if (dp[sum / 2]) cout << "true\n";
        else cout << "false\n";
    }
}