「题解」写点 Luogu 之 0x00

我一直都觉得刷数据结构题单很开心。

直到被神秘构造题卡成✖️。

• 题目链接：P2168 [NOI2015] 荷马史诗 - 洛谷 | 计算机科学教育新生态

---

记录一下一种类哈夫曼树。

void solve() {
    int n, k;
    cin >> n >> k;

    auto cmp = [](const auto& a, const auto& b) {
        if (a.first == b.first)
            return a.second > b.second;
        return a.first > b.first;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq;
    for (int i = 1; i <= n ; i ++) {
        int x;
        cin >> x;
        pq.push({x, 1});
    }
    while ((pq.size() - 1) % (k - 1)) {
        pq.push({0, 1});
    }
    int ans = 0;
    while (pq.size() >= k) {
        int h = -1, w = 0;
        for (int i = 1; i <= k; i ++) {
            auto [l, r] = pq.top();
            pq.pop();
            h = max(h, r);
            w += l;
        }
        ans += w;
        pq.push({w, h + 1});
    }
    cout << ans << "\n" << pq.top().second - 1 << "\n";
}

---

以及

P1364 医院设置 - 洛谷 | 计算机科学教育新生态

void solve() {
    int n;
    cin >> n;
    vector adj(n, vector<int>());
    vector<int> w(n);
    for (int i = 0; i < n; i ++) {
        int ww, u, v;
        cin >> ww >> u >> v;
        w[i] = ww;

        u --, v --;
        if (u > 0) {
            adj[i].push_back(u);
            adj[u].push_back(i);
        }
        if (v > 0) {
            adj[i].push_back(v);
            adj[v].push_back(i);
        }
    }

    vector<int> siz(n);
    vector<int> f(n);

    function<void(int, int, int)> dfs = [&](int u, int fa, int d) {
        siz[u] = w[u];
        int p = adj[u].front();
        for (auto &v : adj[u]) {
            if (v != fa) {
                dfs(v, u, d + 1);
                siz[u] += siz[v];
            }
        }
        f[0] += w[u] * d;
    };
    dfs(0, 0, 0);

    int ans = 0x7f7f7f7f;
    function<void(int, int)> dp = [&](int u, int fa) {
        for (auto &v : adj[u]) {
            if (v != fa) {
                f[v] = f[u] + siz[0] - siz[v] * 2;
                dp(v, u);
            }
        }
        ans = min(ans, f[u]);
    };

    dp(0, 0);
    cout << ans << "\n";
}