Atcoder Beginner Contest 395 题解

发表于 更新于 分类于 阅读次数： 本文字数： 4.3k
好久没打了备战蓝桥杯复健一下，以后省略简单的题吧。

D

题意

给定 \(N\) 个鸽子和 \(N\) 个鸽巢，分别编号为1～\(N\)，初始时所有鸽子都在各自编号对应的巢里。现在给定 \(Q\) 次询问，每次询问给定三种操作：

  1. 把鸽子 \(a\) 移动到巢 \(b\)。
  2. 把 \(a\) 巢和 \(b\) 巢的鸽子互换。
  3. 询问 \(a\) 鸽子在哪个巢。

题解

操作1是很好完成的，我们直接维护下标为 \(i\) 的鸽子的巢即可完成询问。

重点在于操作2，显然不可能直接遍历所有鸽子，既然交换的是巢的编号，所以我们不妨再通过一个映射将鸽子在操作2之前的巢映射到操作2之后的巢，形象一点就是，编号为 \(i\) 的鸽子本来在 \(\text{tag[i]}\) 巢，回答询问3时的结果就是 \(\text{ans[tag[i]]}\)，对于操作2，交换两个巢对应的 \(\text{ans}\) 即可。

然而这样不足以通过，考虑到两个巢交换后又有新的鸽子加入了被交换的巢，这样输出的结果就不正确。为了处理这种情况，我们再引入\(\text{re}\) 数组，含义是 \(\text{re[ans[a]] = a}\)（即找到 \(\text{ans[a]}\) 对应的 \(\text{a}\)），那么现在我们给 \(\text{re,ans,tag}\) 一个更清晰的定义：\(\text{tag[i]}\) 表示第 \(i\) 只鸽子在 \(\text{tag[i]}\) 个位置，\(\text{re[i]}\) 表示第 \(i\) 个位置是第 \(\text{re[i]}\) 个巢，\(\text{ans[i]}\) 表示第 \(i\) 个巢是第 \(\text{ans[i]}\) 个位置（注意区分开位置和巢，我们认为位置就是操作1的结果），这样，对于操作1，我们自然需要使用 \(\text{tag[a] = ans[b]}\)存储位置，这样才能在操作3回答\(\text{re[tag[b]]}\)的巢，操作2交换的一定是位置而不是巢，因为位置是固定的，通过位置找巢是可以变化的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> ans(N + 1), tag(N + 1), re(N + 1);
    for (int i = 1; i <= N; i++) {
        ans[i] = tag[i] = re[i] = i;
    }
    while (Q--) {
        int op, a, b;
        cin >> op >> a;
        if (op == 1) {
            cin >> b;
            tag[a] = ans[b];
        } else if (op == 2) {
            cin >> b;
            swap(ans[a], ans[b]);
            re[ans[a]] = a;
            re[ans[b]] = b;
        } else {
            cout << re[tag[a]] << "\n";
        }
    }
}

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

E

题意

给定一个 \(N\) 个节点，\(M\) 条边的有向图，有两种操作：

  1. 从当前节点沿着有向边花 1 代价走到这条边指向的节点。
  2. 花费 $X $ 的代价，将这张图所有边的方向翻转。

求从 1 号节点走到 \(N\)​ 号节点的最小代价。

题解

我们可以建一张 \(2N\) 个节点的图，\(x\) 指向 \(y\) 的有向边直接连边（原图），同时加入 \(y+N\) 指向 \(x+N\)的有向边（反图），权重均为1，然后建立所有节点 \(x\) 与 \(x+N\)的双向边，代价为 \(X\) ，然后跑 Dijkstra 最短路即可。

正确性大致为：一旦使用操作2，由于所有边均反向，相当于从 \(x\) 走到了 \(x+N\)后在反图继续走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<vector<pair<int, int>>> ver(2 * N + 1);
    for (int i = 1; i <= M; i++) {
        int x, y;
        cin >> x >> y;
        ver[x].push_back({y, 1});
        ver[y + N].push_back({x + N, 1});
    }
    for (int i = 1; i <= N; i++) {
        ver[i].push_back({i + N, X});
        ver[i + N].push_back({i, X});
    }
    vector<int> dis(2 * N + 1, 1e18);
    auto dijkstra = [&](int s = 1) -> void {
        using PII = pair<int, int>;
        priority_queue<PII, vector<PII>, greater<PII>> q;
        q.emplace(0, s);
        dis[s] = 0;
        vector<int> vis(2 * N + 1);
        while (!q.empty()) {
            int x = q.top().second;
            q.pop();
            if (vis[x]) {
                continue;
            }
            vis[x] = 1;
            for (auto [y, w] : ver[x]) {
                if (dis[y] > dis[x] + w) {
                    dis[y] = dis[x] + w;
                    q.emplace(dis[y], y);
                }
            }
        }
    };
    dijkstra(1);
    cout << min(dis[N], dis[N * 2]) << "\n";
}

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

F

题意

\(N\) 对牙，上牙长度\(U[i]\)，下牙长度\(D[i]\)，现在要求每一对牙的长度和都相同，且相邻上牙的高度差的绝对值不能超过\(X\)，可以花费1代价将一颗牙的长度减少 1，求花费的最少代价。

题解

可以通过观察得知最终结果每一对牙的长度最大是初始状态下每对牙之和的最小值，但是还是不能具体确定范围，不妨二分，考虑判断是否成立即可。

对于给定一对牙高度之和判断能否成立，由于只要求了上牙的高度差，因此我们可以确定出上牙的高度范围（最大为初始值，最小是初始值减去能减少的高度）问题转化为对于连续的 \(\text{[a,b]，[a',b']}\)序列，判断\([a',b']\)是否完全包含在\([a-x,b+x]\)​内，此时我们贪心地动态维护符合条件的区间范围即可。

对于成立的高度，求出答案只需要 \(O(N)\) 遍历一次即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N, X;
    cin >> N >> X;
    vector<int> U(N + 1), D(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> U[i] >> D[i];
    }
    int lo = 0, hi = 1e18;
    for (int i = 1; i <= N; i++) {
        hi = min(U[i] + D[i], hi);
    }
    int ans = 8e18;
    int s = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        auto check = [&](int mid) {
            int pre_hi = U[1];
            int pre_lo = max(mid - D[1], 0ll);
            for (int i = 2; i <= N; i++) {
                int lo = max(mid - D[i], 0ll);
                int hi = U[i];
                int cur_lo = max(lo, pre_lo - X);
                int cur_hi = min(hi, pre_hi + X);
                if (cur_lo > cur_hi) {
                    return false;
                }
                pre_lo = cur_lo;
                pre_hi = cur_hi;
            }
            s = 0;
            for (int i = 1; i <= N; i++) {
                s += U[i] + D[i] - mid;
            }
            return true;
        };
        if (check(mid)) {
            ans = min(ans, s);
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";
}

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