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

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

简单题 小红结账

按题意模拟计算。
向上取整可以将分子加上分母再减 ，再计算分子除以分母的向下取整。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(m + 1);
    while (n--) {
        ll k, c;
        cin >> k >> c;
        for (int i = 0; i < k - 1; i++) {
            int x;
            cin >> x;
            a[x] += (c + k - 1) / k;
        }
    }
    for (int i = 1; i <= m; i++)cout << a[i] << ' ';
    return 0;
}

中等题 跳跃游戏(一)

设 为能到达的最远格子。
初值为 。
从 到 ：
当 时，则 位置可到达，同时更新 ：。
最后判定 。

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

困难题 郊区春游

状态压缩dp。
观察到 ，先用floyd求出任意两点间的最短路。
为状压方便，以下第 位等都以 开始。
表示游览状态为 ，最后一个游览第 个郊区的最小花费。
游览状态是什么？用 位二进制位表示状态，第 位为 表示第 个景区未被游览过，否则为被游览过。
初始状态：，否则为 。
枚举 ， 为状态，从 到 ， 为郊区，从 到 。
当 表示的状态中， 已被游览过且 未被游览过，就可以转移状态了。
即 。
判别 表示的状态中 的游览状态，可以将 右移 位并和 做按位与，结果为 则已游览过，否则未游览过。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, R;
    cin >> n >> m >> R;
    vector<vector<int>> dis(n, vector<int>(n, 1e9));
    for (int i = 0; i < n; i++)
        dis[i][i] = 0;
    vector<int> V(R);
    for (int i = 0; i < R; i++)cin >> V[i];
    for (int i = 0; i < R; i++)V[i]--;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        dis[a - 1][b - 1] = c;
        dis[b - 1][a - 1] = c;
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    vector<vector<int>> dp(1 << R, vector<int>(R, 1e9));
    for (int i = 0; i < R; i++)
        dp[1 << i][i] = 0;
    for (int i = 0; i < (1 << R); i++) {
        for (int j = 0; j < R; j++) {
            for (int k = 0; k < R; k++) {
                if (j == k)continue;
                if ((((i >> j) & 1) == 1) && (((i >> k) & 1) == 0)) {
                    dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dis[V[j]][V[k]]);
                }
            }
        }
    }
    cout << *min_element(dp[(1 << R) - 1].begin(), dp[(1 << R) - 1].end()) << '\n';
    return 0;
}