352

A - AtCoder Line

AtCoder 铁路线有 $N$ 个车站，编号为 $1, 2, \dots, N$ 。

在这条线路上，有趟进站列车从 $1$ 站出发，依次停靠 $2, 3, \dots, N$ 站，有趟出站列车从 $N$ 站出发，依次停靠 $N - 1, N - 2, \dots, 1$ 站。

高桥站即将从 $X$ 站前往 $Y$ 站，只需使用进站和出站列车中的一列。

求这趟列车在 $Z$ 站是否停车。

void solve() {
    int n, x, y, z;cin >> n >> x >> y >> z;
    if (z <= y && z >= x || z <= x && z >= y) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B - Typing

高桥尝试使用键盘输入由小写英文字母组成的字符串 $S$ 。

他打字时只看键盘，不看屏幕。

每当他错误地输入一个不同的小写英文字母时，他就立即按下退格键。然而，退格键被破坏了，因此误键入的字母没有被删除，实际键入的字符串是 $T$ 。

他没有误按小写英文字母以外的任何键。

$T$ 中未被误输入的字符称为正确输入字符。

确定正确键入的字符在 $T$ 中的位置。

void solve() {
    string s, t;cin >> s >> t;s = ' ' + s;t = ' ' + t;
    int j = 1;
    for (int i = 1;i < t.size();i++) {
        if (t[i] == s[j]) {
            cout << i << " ";j++;
        }
    }
}

C - Standing On The Shoulders

有 $N$ 个巨人，他们的名字分别是 $1$ 到 $N$ 。当巨人 $i$ 站在地上时，他们的肩高是 $A_{i}$ ，头高是 $B_{i}$ 。

你可以选择 $(1, 2, \dots, N)$ 的排列组合 $(P_{1}, P_{2}, \dots, P_{N})$ ，并根据以下规则堆叠 $N$ 个巨人：

首先，将 $P_{1}$ 巨人放在地上。巨人 $P_{1}$ 的肩膀距离地面的高度为 $A_{P_{1}}$ ，头部距离地面的高度为 $B_{P_{1}}$ 。
为了 $i = 1, 2, \dots, N - 1$ 的顺序，要把巨人 $P_{i + 1}$ 放在巨人 $P_{i}$ 的肩膀上。如果巨人 $P_{i}$ 的肩膀距离地面的高度是 $t$ ，那么巨人 $P_{i + 1}$ 的肩膀距离地面的高度就是 $t + A_{P_{i + 1}}$ ，他们的头距离地面的高度就是 $t + B_{P_{i + 1}}$ 。

求最上面的巨人 $P_{N}$ 的头部距离地面的最大可能高度。

#define int long long
void solve() {
    int n;cin >> n;;
    int sum = 0, mx = -1, ans = 0;
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;sum += y;sum -= y - x;
        mx = max(mx, y - x);
    }
    cout << sum + mx << '\n';
}

D - Permutation Subsequence

给你一个 $(1, 2, \dots, N)$ 的排列组合 $P = (P_{1}, P_{2}, \dots, P_{N})$ 。

如果一个索引序列 $(i_{1}, i_{2}, \dots, i_{K})$ 同时满足以下两个条件，那么这个索引序列被称为好索引序列：

$1 \leq i_{1} < i_{2} < \dots < i_{K} \leq N$ .
子序列 $(P_{i_{1}}, P_{i_{2}}, \dots, P_{i_{K}})$ 可以通过重新排列一些连续的 $K$ 整数得到。
形式上，存在一个整数 $a$ ，使得 ${P_{i_{1}}, P_{i_{2}}, \dots, P_{i_{K}}} = {a, a + 1, \dots, a + K - 1}$ .

求所有好的索引序列中 $i_{K} - i_{1}$ 的最小值。可以证明，在此问题的约束条件下，至少存在一个好的索引序列。

按照 $p$ 排列从 $[1, k]$ 到 $[n - k + 1, n]$ 的所有可能中取最小值即可。有点滑动窗口的意思了。

void solve() {
    int n, k;cin >> n >> k;vector<int> mp(n + 1);
    for (int i = 1;i <= n;i++) {
        int x; cin >> x; mp[x] = i;
    }
    set<int> s;
    for (int i = 1;i <= k;i++) {
        s.insert(mp[i]);
    }
    int ans = *s.rbegin() - *s.begin();
    for (int i = k + 1;i <= n;i++) {
        s.erase(mp[i - k]);
        s.insert(mp[i]);
        ans = min(ans, *s.rbegin() - *s.begin());
    }
    cout << ans << '\n';
}

E - Clique Connect

给你一个加权无向图 $G$ ，其中有 $N$ 个顶点，编号为 $1$ 至 $N$ 。最初， $G$ 没有边。

您将执行 $M$ 次操作为 $G$ 添加边。 $i$ -th 操作 $(1 \leq i \leq M)$ 如下：

给你一个由 $K_{i}$ 个顶点组成的顶点子集 $S_{i} = {A_{i, 1}, A_{i, 2}, \dots, A_{i, K_{i}}}$ 。对于每一对 $u, v$ ，即 $u, v \in S_{i}$ 和 $u < v$ ，在顶点 $u$ 和 $v$ 之间添加一条边，权重为 $C_{i}$ 。

完成所有 $M$ 操作后，确定 $G$ 是否相连。如果是，求 $G$ 最小生成树中各条边的总重。

Solution

最小生成树/Prim/Kruskal

最小生成树板题。

小技巧：这里如果暴力读入会超时，只要一个点与后面的点依次连接不影响结果

Prim

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<pair<int, int>>>g(n + 1);
    while (m--) {
        int k, c;cin >> k >> c;
        int h;cin >> h;
        for (int i = 1;i < k;i++) {
            int x;cin >> x;
            g[h].push_back({x,c});
            g[x].push_back({h,c});
        }
    }
    int ans = 0, cnt = 0;
    vector<int> d(n + 1, 1e18), vis(n + 1);
    priority_queue<pair<int, int>>q;
    d[1] = 0;q.push({0,1});
    while (q.size()) {
        auto u = q.top().second;q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        ans += d[u];cnt++;
        for (auto [v, w] : g[u]) {
            if (d[v] > w) {
                d[v] = w;q.push({-d[v],v});
            }
        }
    }
    if (cnt == n){
        cout << ans << '\n';
    } else {
        cout << "-1\n";
    }
}

Kruskal

#define int long long
int f[200010];
int find(int x) {
    if (f[x] == x)return x;
    return f[x] = find(f[x]);
}
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)f[i] = i;

    vector<array<int, 3>> g;
    for (int i = 1;i <= m;i++) {
        int k, c;cin >> k >> c;
        int h;cin >> h;
        for (int i = 1;i < k;i++) {
            int x;cin >> x;
            g.push_back({h,x,c});
        }
    }
    sort(g.begin(), g.end(), [&](auto x, auto y) {
        return x[2] < y[2];
        });
    int ans = 0, cnt = 0;
    for (int i = 0;i < g.size();i++) {
        int u = find(g[i][0]), v = find(g[i][1]);
        if (u == v)continue;
        ans += g[i][2];f[u] = v;
        if (++cnt == n - 1)break;
    }
    if (cnt != n - 1) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }
}

F - Estimate Order

有 $N$ 人，编号为 $1$ 至 $N$ 。

在这些 $N$ 人中举行了一次竞赛，并对他们进行了相应的排名。以下是他们的排名信息：

每个人都有一个唯一的排名。
对于每个 $1 \leq i \leq M$ ，如果 $A_{i}$ 的排名是 $x$ -th，而 $B_{i}$ 的排名是 $y$ -th，那么就是 $x - y = C_{i}$ 。

给定的输入保证了至少有一种可能的排名与给定的信息不矛盾。

回答 $N$ 个查询。 $i$ -th 查询的答案是一个整数，确定方法如下：

如果可以唯一确定人 $i$ 的排名，则返回该排名。否则，返回 $- 1$ 。

Solution

(待更 $\dots$ )