Atcoder Beginner Contest 376 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.2k
挺不错的一场，涉及二分、图论、贪心、dp等多种题型，适合学习。

AtCoder Beginner Contest 376题解

A

题意

按按钮可以获得糖果，给定一些按下的时间和常数C。第一次按下按钮必定获得糖果，之后需要两次之间的间隔大于等于C。求能获得的糖果数。

题解

没什么好说的，模拟即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, c;
    cin >> n >> c;
    int ans = 0;
    int last = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if (i == 0) {
            ans++;
            last = v;
            continue;
        }
        if (v - last >= c) {
            ans++;
            last = v;
        }
    }
    cout << ans << "\n";
}

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

B

题意

给定一个大小为\(n\)的环，首尾相接，依次编号为\(1,2,...,n\)，\(n\)过后是\(1\)。初始左手和右手分别放在\(1\)位置和\(2\)位置，现在给出\(q\)次操作，每次给定要操作的手和移动到的位置，一次操作只能动一只手，且任何时候两只手不能重合。求最后所有操作一共移动了多少距离。

题解

由于一次只能动一只手，所以如果另一只手在当前位置和要到达的位置之间，就不能经过它，必须走另一个方向。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    array<int, 2> a{0, 1};
    int ans = 0;
    while (q--) {
        char s;
        int d;
        cin >> s >> d;
        d--;
        auto work = [&](int i, int x) {
            if (abs(a[!i] - a[i]) + abs(a[!i] - x) == abs(a[i] - x)) {
                ans += n - abs(a[i] - x);
            } else {
                ans += abs(a[i] - x);
            }
            a[i] = x;
        };
        work(s == 'L' ? 0 : 1, d);
    }
    cout << ans << "\n";
}

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

C

题意

给定\(n\)个玩具的大小和\(n-1\)个盒子的大小，只有盒子的大小不小于玩具时，玩具才能放到盒子里。现在需要再增加一个盒子，要求每个盒子都必须且只能放一个玩具，求新增的盒子的大小的最小值，或输出-1代表不可能。

题解

求最小值可以考虑二分。我们不妨将玩具的大小排序，然后新增一个盒子后将盒子的大小也进行排序，这样必须要一一对应才满足条件，否则继续二分。

注意一下二分写法上的细节：例如while(l < r)还是用“\(\le\)”，更新时是直接赋值mid还是mid+1或mid-1？建议养成自己习惯的写法。

如果规定左闭右开区间，应该是while(l < r)，因为l == r时区间应该为空，更新时r = mid时应该是取不到r的，配合上二分时更新答案可以避免出错。

这样做的话，每次二分需要一次排序，时间复杂度是\(O(n\log n\log A)\)，足够通过本题了。

还有一种\(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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> b[i];
    }
    sort(a.begin(), a.end());
    int l = 0, r = 2e9;
    int ans = 1e18;
    while (l < r) {
        int mid = (l + r) / 2;
        b[n - 1] = mid;
        vector<int> c(b.begin(), b.end());
        sort(c.begin(), c.end());
        bool ok = 1;
        for (int i = 0; i < n; i++) {
            if (a[i] > c[i]) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            r = mid;
            ans = min(ans, mid);
        } else {
            l = mid + 1;
        }
    }
    if (ans == 1e18) {
        ans = -1;
    }
    cout << ans << "\n";
}

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

D

题意

给定一张有向图，判断是否存在从\(1\)开始的环，输出环的大小或者-1代表不存在。

题解

找环的一个方法就是拓扑排序，即从起点BFS后看是否回到起点。

但是本题还要求环的大小，考虑到如果去掉环中连回出发点的边，那么从起点到各个点的最短路是可以确定的，那么现在将连回来，环的大小可以视为自己到自己的最短路。设\(dis[v]\)代表从出发点到\(v\)的最短路，BFS的过程中更新即可，同时\(dis\)数组还可以充当一个vis数组的作用。如果回到起点再特判即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        e[x].push_back(y);
    }
    int ans = 1e9;
    queue<int> q;
    q.push(0);
    vector<int> dis(n, -1);
    dis[0] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : e[u]) {
            if (v == 0) {
                ans = min(ans, dis[u] + 1);
            }
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    if (ans == 1e9) {
        ans = -1;
    }
    cout << ans << "\n";
}

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

E

题意

给定两个大小为\(n\)的数组\(A_i\)和\(B_i\)，求\(max_{i\in S}{A_i}\times\sum_{i\in S}B_i\)的最小值，其中\(S\)是一个大小为\(K\)的集合，可以从\(1\)~\(n\)中选取。

题解

对于两个数组，似乎没有那么好办，由于要求整体的最小值，第一想法应该是让乘号两边的数都尽量小，然而在选取\(K\)个下标的情况下也并不是那么好做。

这种情况可以考虑的做法是固定一边，然后单独考虑另一边的情况。显然乘号左边是更容易处理的，我们直接将\(A\)数组排序，从小到大即可枚举最大值，这样做的另一个好处是最大值确定下来了，选择的范围也只能是从更小的数而不能在更大的数中选择了，否则会最大值就不是当前钦定的了。

固定最大值后，贪心显然是成立的：我们需要让乘号右边的和尽量小。考虑使用一个优先队列（堆），每次选择一个最大值后也把同下标的\(B_i\)加入到堆里，然后弹出堆顶的元素直到堆的大小为\(K\)（优先队列默认是大根堆），此时就是当前钦定最大值的最优情况了，我们在枚举最大值的过程中更新答案即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    vector<int> c(n);
    iota(c.begin(), c.end(), 0);
    sort(c.begin(), c.end(), [&](int i, int j) { return a[i] < a[j]; });
    int sum = 0;
    int ans = 1e18;
    priority_queue<int> pq;
    for (auto i : c) {
        sum += b[i];
        pq.push(b[i]);
        while (pq.size() > k) {
            sum -= pq.top();
            pq.pop();
        }
        if (pq.size() == k) {
            ans = min(ans, sum * a[i]);
        }
    }
    cout << ans << "\n";
}

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

F

题意

给定一个大小为\(n\)的环，首尾相接，依次编号为\(1,2,...,n\)，\(n\)过后是\(1\)。初始左手和右手分别放在\(1\)位置和\(2\)位置，现在给出\(q\)​次操作，每次给定要操作的手和移动到的位置，每次操作两只手都能移动，且任何时候两只手不能重合。求最后所有操作一共移动了多少距离。

\(3\le n\le 3000,1\le q\le 3000\)

题解

B题的升级版，限制改为了每次操作两只手都能移动，这样的限制下，如果另一只手在要操作的手和目的地之间，我们就可以直接从选择的方向移动，这样会把另一只手移动到目的地之后一个位置，也可以按照B题的想法。这样我们不能仅仅只考虑每次操作的最优解了，因为也许我们让另一只手提前移动一些距离能让后面的状态更优。如果说B题是贪心地进行每次操作的话，本题应该是dp（从数据范围也可以推测出来）。

首先是状态设计，如果是\(dp[i][j][k]\)代表第\(i\)次操作，两只手分别在\(i\)位置和\(j\)位置的话，显然会超时，考虑优化。

我们知道，每次操作不管怎么做，给定的那只手一定会放在给定的位置，因此我们在状态转移时并不需要遍历给定的那只手的状态，只需要考虑另一只手即可。那么我们设\(dp[i][j]\)代表第\(i\)次操作，没有给定的那只手在\(j\)​位置，所有操作所移动的距离总数。但是，这样做的话，如果连续两次操作的手不一样，那么转移时并不能对应的上（毕竟上一次和这一次的手不同，对应的含义也有区别）。在这种情况下，我们考虑交换上一次的两只手，保证两次操作的都是同一只手。这样做可行的原因是其实上一次操作的状态已经全部得到，但是只有一个状态能继续转移。

接下来考虑状态转移方程，我们需要从上一个状态的两只手的位置转移过来，现在已知一只手的目的地，显然需要考虑两种情况：顺时针移动和逆时针移动（其中一种是B题的方法，另一种是将另一只手移动到目的地后一个位置，即“挤开”），设目的地为\(b\)，要移动的手之前的位置为\(x\)，另一只手的位置为\(y\)，分别需要移动\(dx,dy\)，那么转移方程应该有：\(dp[i][b + 1] = dp[i-1][x] + dx + dy + 1\)或\(dp[i][y] = dx + dp[i-1][x]\)，分别对应“挤开”和B题的情况。注意\(b+1\)应该在模意义下（即考虑循环），还需要考虑从另一个方向移动，同理，只有\(dx,dy\)​不同。

还可以通过滚动数组的方式优化空间。

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
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    const int inf = 1e9;
    vector<int> dp(n, inf);
    dp[1] = 0;
    int h = 0, x = 0;
    while (q--) {
        int a, b;
        char c;
        cin >> c >> b;
        b--;
        a = (c == 'L' ? 0 : 1);
        vector<int> ndp(n, inf);
        auto work = [&](int x, int y, int a, int d) {
            int dx = (a - x + n) % n;
            int dy = (a - y + n) % n;
            if (dx >= dy) {
                ndp[(a + 1) % n] = min(ndp[(a + 1) % n], d + dx + dy + 1);
            } else {
                ndp[y] = min(ndp[y], d + dx);
            }
            dx = (x - a + n) % n;
            dy = (y - a + n) % n;
            if (dx >= dy) {
                ndp[(a - 1 + n) % n] =
                    min(ndp[(a - 1 + n) % n], d + dx + dy + 1);
            } else {
                ndp[y] = min(ndp[y], d + dx);
            }
        };
        if (a == h) {
            for (int j = 0; j < n; j++) {
                if (dp[j] == inf) {
                    continue;
                }
                work(x, j, b, dp[j]);
            }
        } else {
            for (int j = 0; j < n; j++) {
                if (dp[j] == inf) {
                    continue;
                }
                work(j, x, b, dp[j]);
            }
        }
        h = a;
        x = b;
        dp = ndp;
    }
    int ans = *min_element(dp.begin(), dp.end());
    cout << ans << "\n";
}

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