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

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

简单题 游游的整数切割

如果字符串最后一位是奇数，那能被切割的位置个数为字符串的奇数个数。
如果字符串最后一位是偶数，那能被切割的位置个数为字符串的偶数个数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    long long ji = 0, ou = 0;
    for (auto it : s) {
        if ((it - '0') % 2 == 0)ou++;
        else ji++;
    }
    long long ans = 0;
    if ((s[s.length() - 1] - '0') % 2 == 1)cout << ji - 1;
    else cout << ou - 1;
    return 0;
}

中等题 矩阵的最小路径和

动态规划。
设 为走到 时的最大路径和。
除了最左边一列和最上面一行，其他的格子只有两种来路：左边的格子和上面的格子。
那直接取这两个格子 小的那一个再加上 。
最左边一列的格子只能从它上面的格子走来。
最上面一行的格子只能从它左边的格子走来。
这两种格子转移来源只有一种。
直接上转移方程：

1. 当 时，。
2. 当 时，。
3. 以上两种都不满足，。

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

困难题 旅游

树形dp。
用 表示以 为根时的最大游览天数，如果 表示不在 住宿，否则表示在 住宿。
从根节点 往下dfs，dfs到 时先将 设为 ，然后dfs其所有子节点。
子节点dfs完成后需要回溯到 开始计数，设 的一个子节点为 。
如果在 住宿过，则 一定不能住宿，所以 。
如果在 没有住宿过，则 可住宿可不住宿，取两种情况的最大值，所以 。
最后输出 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, s;
    cin >> n >> s;
    vector<vector<int>> ver(n + 1);
    vector<array<int, 2>> dp(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    auto dfs = [&](auto&& self, int i, int fa)->void {
        dp[i][1] = 1;
        for (auto it : ver[i])
            if (it != fa) {
                self(self, it, i);
                dp[i][1] += dp[it][0];
                dp[i][0] += max(dp[it][0], dp[it][1]);
            }
    };
    dfs(dfs, s, 0);
    cout << dp[s][1] << '\n';
    return 0;
}