西南财经大学·奇点工作室·程序设计部 暑期训练营 第五次课后习题题解

A. tokitsukaze 与士兵

题目链接：A. tokitsukaze 与士兵

考察知识点：贪心、优先队列

读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列顶端的士兵战力（即最低战力）从 cnt 中减去，直到优先队列大小不超过当前士兵的 s[i] 值为止（由于已经进行了降序排序，所以当前的 s[i] 一定是已选择士兵中最低的 s 值），每次更新答案 ans 为 max(ans, cnt)。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vpii vec(n);
    for (int i = 0; i < n; i++)
    {
        int v, s;
        cin >> v >> s;
        vec[i] = {s, v};
    }
    sort(vec.begin(), vec.end(), greater<pii>());
    priority_queue<int, vi, greater<int>> pq;  // 小根堆
    ll cnt = 0, ans = 0;
    for (int i = 0; i < n; i++)
    {
        int v = vec[i].second, s = vec[i].first;
        cnt += v;
        pq.push(v);
        while (pq.size() > s)
        {
            cnt -= pq.top();
            pq.pop();
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

B. 建筑抢修

题目链接：B. 建筑抢修

考察知识点：贪心、优先队列

和 A 题类似，读入每个建筑的信息，按照每个建筑修理的截止时间 t2 升序排序，然后依次将建筑修理的时间 t1 加入优先队列（大根堆），同时维护当前建筑修理的时间之和 time，当当前建筑修理完成后的时间大于截止时间时，如果当前建筑所需的修理时间 t1 小于优先队列顶端的建筑所需的修理时间（即最长修理时间）时，则将当前建筑与优先队列顶端的建筑交换，同时更新 time 为 time - pq.top() + t1，最后的优先队列大小即为最多可修理的建筑数量。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vpll t(n);
    for (int i = 0; i < n; i++)
    {
        ll t1, t2;
        cin >> t1 >> t2;
        t[i] = {t2, t1};
    }
    sort(t.begin(), t.end());
    priority_queue<ll, vl, less<ll>> pq; // 大根堆
    ll time = 0;
    for (int i = 0; i < n; i++)
    {
        ll t1 = t[i].second, t2 = t[i].first;
        if (time + t1 <= t2)
        {
            pq.push(t1);
            time += t1;
        }
        else if (!pq.empty() && pq.top() > t1)
        {
            time -= pq.top() - t1;
            pq.pop();
            pq.push(t1);
        }
    }
    cout << pq.size() << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

C. 缓存交换

题目链接：C. 缓存交换

考察知识点：贪心、优先队列

模拟操作系统 MIN/OPT 换页机制，每次换页优先选择未来不会再访问的页或者在最长一段时间不会再访问的页（即当前缓存页中下次最晚访问的页），具体实现请见代码。

理论上，MIN/OPT 换页机制 是最优的内存换页机制，但是由于需要预知未来的访问情况，所以在实际应用中无法使用，只能作为一种理论参考。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n, m;
    cin >> n >> m;
    vi id(n + 1);
    for (int i = 0; i < n; i++)
        cin >> id[i];
    map<int, int> mp; // 记录每个id最后出现的位置
    vi next(n + 1);   // 下一次出现的位置
    for (int i = n; i >= 0; i--)
    {
        if (mp[id[i]] == 0)
            next[i] = n;
        else
            next[i] = mp[id[i]];
        mp[id[i]] = i;
    }
    vector<bool> cache(n + 1, false); // 是否在缓存中
    priority_queue<int> pq;           // 大根堆
    int ans = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (cache[i])
        {
            cache[next[i]] = true;
            pq.push(next[i]);
        }
        else
        {
            if (cnt == m)
            {
                cache[pq.top()] = false;
                pq.pop();
            }
            else
                cnt++;
            cache[next[i]] = true;
            pq.push(next[i]);
            ans++;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

D. 网络优化

题目链接：D. 网络优化

考察知识点：贪心、优先队列

读入服务器的信息，按照 (l, r, v) 升序排序，遍历每一位用户，为每一位用户分配符合条件的服务器中 r 最小的服务器，对应的服务器的 v 值减一，若成功为用户分配服务器，则答案 ans 加一。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

struct Node
{
    int l, r, v;
    bool operator<(const Node &s) const
    {
        if (l != s.l)
            return l < s.l;
        if (r != s.r)
            return r < s.r;
        else
            return v < s.v;
    }
};

struct cmp
{
    bool operator()(const Node &a, const Node &b)
    {
        if (a.r != b.r)
            return a.r > b.r;
        else
            return a.v > b.v;
    }
};

void solve()
{
    int n, m;
    while (cin >> n >> m)
    {
        vector<Node> server(m);
        for (int i = 0; i < m; i++)
            cin >> server[i].l >> server[i].r >> server[i].v;
        sort(server.begin(), server.end());
        priority_queue<Node, vector<Node>, cmp> pq;  // 小根堆
        int cur = 0, ans = 0;
        for (int i = 1; i <= n; i++)
        {
            while (server[cur].l <= i)
            {
                pq.push(server[cur]);
                cur++;
            }
            while (!pq.empty() && (pq.top().r < i || !pq.top().v))
                pq.pop();
            if (pq.empty())
                continue;
            auto tmp = pq.top();
            tmp.v--;
            pq.pop();
            pq.push(tmp);
            ans++;
        }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

E. 合并果子

题目链接：E. 合并果子

考察知识点：贪心、优先队列、哈夫曼树

题目翻译一下就是 个节点构成一棵二叉树，求这棵树的最小带权路径长度。

哈夫曼树 是带权路径长度最小的树，所以本题只需要构造一棵哈夫曼树即可。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    priority_queue<int, vi, greater<int>> pq;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        pq.push(a);
    }
    int ans = 0;
    while (pq.size() > 1)
    {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

F. 生成树

题目链接：F. 生成树

考察知识点：生成树

本题其实不用建树，对比两棵树的差异即可，当生成树 a 有而生成树 b 没有的边的数量不等于生成树 a 没有而生成树 b 有的边的数量时输出 -1（事实上，可以证明对于两棵节点相同的生成树，这两个值一定相等），否则输出相差边数之和的一半。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    while (cin >> n)
    {
        set<pii> s;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            s.insert({u, v});
        }
        int ans = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            if (s.count({u, v}))
                s.erase({u, v});
            else if (s.count({v, u}))
                s.erase({v, u});
            else
                ans++;
        }
        if (ans != s.size())
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

G. 树的路径

题目链接：G. 树的路径

考察知识点：树上 DFS

设节点 i 到根节点 1 的距离为节点 i 的长度，记为 dist[i]，则有以下结论：

• 长度为偶数的两个节点之间的路径长度一定为偶数
• 长度为奇数的两个节点之间的路径长度也一定为偶数

因此本题我们只需要遍历整棵树，记录每个节点的长度，然后统计长度为偶数的节点数量 和长度为奇数的节点数量 ，长度为偶数的路径的数量即为 。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 1e6 + 5;

vi edges[N];
int dist[N];

void dfs(int u, int from)
{
    dist[u] = dist[from] + 1;
    for (int v : edges[u])
        if (v != from)
            dfs(v, u);
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(1, 0);
    ll cnt[2] = {0, 0};
    for (int i = 1; i <= n; i++)
        cnt[dist[i] % 2]++;
    cout << cnt[0] * (cnt[0] - 1) / 2 + cnt[1] * (cnt[1] - 1) / 2 << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

H. 漂亮的公园

题目链接：H. 漂亮的公园

考察知识点：树上 DFS、倍增、LCA

设 为颜色 的两个直径端点（即距离最远的两个点）， 为颜色 中的一个点，则点 到颜色 中点的最大距离为 。 可以想象一个点到一条线段的最远距离必然出现在这个点到两个端点的距离中，在此不做严格证明。

进而我们有如下结论： 设 为颜色 的两个直径端点， 为颜色 的两个直径端点，则颜色 中的点到颜色 中点的最大距离为 。 特殊的，当某种颜色的点不足两个时，结论可以简化。

因此我们的任务就变成了查找每种颜色距离最远的两个点。

我们使用 LCA （最近公共祖先）来计算树中每两点间的距离：

其中， 表示点 的深度（即点 到根节点的距离）。

对于代码中一些变量的解释如下：

• edges[i]：点 的所有连边
• fa[i][j]：点 向上 步的点（即点 的第 代祖先）
• dep[i]：点 的深度（到根节点的距离）
• lg[i]：（ 向下取整）
• mp[x] 颜色为 的所有点
• longest[x] 颜色 的直径端点（颜色 中距离最远的两点）

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 1e5 + 5, LOGN = 20;
vector<int> edges[N];
int c[N], fa[N][LOGN];
int dep[N], lg[N];
map<int, vi> mp;
map<int, pii> longest;

void dfs(int u, int from)
{
    mp[c[u]].push_back(u); // 记录颜色为 c[u] 的点
    dep[u] = dep[from] + 1;
    fa[u][0] = from; // 记录父节点
    for (int i = 1; 1 << i <= dep[u]; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 记录 2^i 祖先
    for (int v : edges[u])                  // 遍历所有子节点
        if (v != from)
            dfs(v, u);
}

int lca(int x, int y) // 求 x 和 y 的最近公共祖先
{
    if (dep[x] < dep[y]) // 保证 x 深度大于 y
        swap(x, y);
    while (dep[x] > dep[y]) // 先将 x 跳到和 y 一样深
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) // 如果 x 和 y 相等，说明 y 是 x 的祖先
        return x;
    for (int i = lg[dep[x]] - 1; i >= 0; i--) // 从 x 开始向上跳
        if (fa[x][i] != fa[y][i])             // 如果 x 和 y 的 2^i 祖先不同
            x = fa[x][i], y = fa[y][i];       // 同时跳
    return fa[x][0];
}

int dis(int x, int y) // 求 x 和 y 的距离
{
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < N; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); // 预处理 log2
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1, 0);
    for (auto item : mp) // 预处理每种颜色距离最远的两个点
    {
        int color = item.first;
        vi &nodes = item.second;
        longest[color] = {nodes[0], nodes[0]};
        for (int i = 1; i < nodes.size(); i++)
        {
            int a = dis(longest[color].first, nodes[i]);
            int b = dis(longest[color].second, nodes[i]);
            if (a < b)
            {
                swap(a, b);
                swap(longest[color].first, longest[color].second);
            }
            if (a > dis(longest[color].first, longest[color].second))
                swap(longest[color].second, nodes[i]);
        }
    }
    while (q--)
    {
        int x, y, ans = 0;
        cin >> x >> y;
        if (mp.count(x) && mp.count(y))
        {
            int x1 = longest[x].first, x2 = longest[x].second;
            int y1 = longest[y].first, y2 = longest[y].second;
            ans = max({dis(x1, y1), dis(x1, y2), dis(x2, y1), dis(x2, y2)});
        }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

I. 城市网络

题目链接：I. 城市网络

考察知识点：树上 DFS、倍增

本题很容易想到模拟的方式，但时间复杂度为 ，会超时。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 1e5 + 5;
vector<int> edges[N];
int fa[N], a[N];

void dfs(int u, int from)
{
    fa[u] = from;
    for (int v : edges[u])
        if (v != from)
            dfs(v, u);
}

void query(int u, int v, int c)
{
    int ans = 0, m = c;
    while (u != fa[v])
    {
        if (a[u] > m)
            ans++;
        m = max(m, a[u]);
        u = fa[u];
    }
    cout << ans << endl;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1, 0);
    while (q--)
    {
        int u, v, c;
        cin >> u >> v >> c;
        query(u, v, c);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

使用 倍增 来优化程序，我们不用每次只向上跳一步，而是每次向上跳 步。

详解如下代码，其中 fa[i][j] 为从 i 点开始，购买了 次珠宝的节点，dep[i] 为节点 i 到根节点的距离（即深度），to[i] 为第 次询问的终点，a[n + i] 为第 次询问的初始珠宝价值。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 2e5 + 5, LOGN = 20;
vector<int> edges[N];
int a[N], fa[N][LOGN];
int dep[N], to[N];

void dfs(int u, int from)
{
    dep[u] = dep[from] + 1;
    int f0 = from;
    // fa[u][0] 为从 u 节点出发，购买了 2^0 = 1 次珠宝的节点
    if (a[from] > a[u]) // 如果父节点刚好是满足条件的节点
        fa[u][0] = from;
    else // 否则向上跳
    {
        for (int i = LOGN - 1; i >= 0; i--)            // 从大到小枚举
            if (fa[from][i] && a[fa[from][i]] <= a[u]) // 从父节点开始向上跳
                from = fa[from][i];
        fa[u][0] = fa[from][0]; // 事实上，fa[u][0] 就是 u 往上走的第一个 a 值比 u 大的节点
    }
    for (int i = 1; i < LOGN; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 2^i = 2^(i-1) + 2^(i-1)
    for (int v : edges[u])                  // 遍历所有子节点
        if (v != f0)
            dfs(v, u);
}

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    for (int i = 1; i <= q; i++) // 为了考虑 u 点
    {
        int u, v, c;
        cin >> u >> v >> c;
        edges[i + n].push_back(u);
        edges[u].push_back(i + n);
        to[i] = v, a[i + n] = c;
    }
    dfs(1, 0);
    for (int i = 1; i <= q; i++)
    {
        int u = n + i, v = to[i], ans = 0;
        for (int i = LOGN - 1; i >= 0; i--)
            if (dep[fa[u][i]] >= dep[v]) // 尝试向上跳 2^i 步
            {
                u = fa[u][i];
                ans += 1 << i;
            }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}