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

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

简单题 表示数字

当 是数字且 不是数字，或 不是数字且 是数字时添加 。
注意特判字符串开头和结尾是数字的情况。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool isnum = 0;
    string ans;
    for (auto it : s) {
        if (isdigit(it) ^ isnum) {
            ans += '*';
            isnum ^= 1;
        }
        ans += it;
    }
    if (isnum)ans += '*';
    cout << ans << '\n';
    return 0;
}

中等题 球格模型（简单版）

假设长边是 ，短边是 ，前 个球中每一个球可以同时填一行一列，之后 个球每一个球可以填一行，剩余的球任意放。
当球的数量 时则不够放。

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

困难题 【模板】01背包

和普通01背包不同的是，需要多一个 状态记录这个体积能否被装到。
记录 状态其实就是周三的装箱问题。
只有当 时才能转移状态，转移方程：。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, V;
    cin >> n >> V;
    vector<int> dp(V + 1);
    vector<bool> vis(V + 1);
    vis[0] = 1;
    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int i = V; i >= v; i--) {
            if (vis[i - v]) {
                dp[i] = max(dp[i], dp[i - v] + w);
                vis[i] = 1;
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
    cout << dp[V] << '\n';
    return 0;
}