活動地址： ?？痛赫兴㈩}訓(xùn)練營 - 編程打卡活動

簡單題 小紅結(jié)賬

按題意模擬計算。
向上取整可以將分子加上分母再減 ，再計算分子除以分母的向下取整。

#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;
}

中等題 跳躍游戲(一)

設(shè) 為能到達(dá)的最遠(yuǎn)格子。
初值為 。
從 到 ：
當(dāng) 時，則 位置可到達(dá)，同時更新 ：。
最后判定 。

#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;
}

困難題 郊區(qū)春游

狀態(tài)壓縮dp。
觀察到 ，先用floyd求出任意兩點(diǎn)間的最短路。
為狀壓方便，以下第 位等都以 開始。
表示游覽狀態(tài)為 ，最后一個游覽第 個郊區(qū)的最小花費(fèi)。
游覽狀態(tài)是什么？用 位二進(jìn)制位表示狀態(tài)，第 位為 表示第 個景區(qū)未被游覽過，否則為被游覽過。
初始狀態(tài)：，否則為 。
枚舉 ， 為狀態(tài)，從 到 ， 為郊區(qū)，從 到 。
當(dāng) 表示的狀態(tài)中， 已被游覽過且 未被游覽過，就可以轉(zhuǎn)移狀態(tài)了。
即 。
判別 表示的狀態(tài)中 的游覽狀態(tài)，可以將 右移 位并和 做按位與，結(jié)果為 則已游覽過，否則未游覽過。

#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;
}