Atcoder Beginner Contest 388 题解

发表于 更新于 分类于 阅读次数： 本文字数： 3.3k
很久没打了，复健一下，题目挺简单但是没打好。

HHKB Programming Contest 2025(AtCoder Beginner Contest 388) 题解

A

题意

输出一个字符串的首字母加上“UPC”。

题解

没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    cout << s[0] << "UPC" << "\n";
}

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

B

题意

给定 \(N\) 条蛇的长度和宽度，重量由二者之积决定。给定 \(D\) ,对于所有 \(1\le k\le D\)，找到长度增加 \(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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N, D;
    cin >> N >> D;
    vector<int> T(N), L(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i] >> L[i];
    }
    for (int i = 1; i <= D; i++) {
        int mx = 0;
        for (int j = 0; j < N; j++) {
            mx = max(mx, T[j] * (L[j] + i));
        }
        cout << mx << "\n";
    }
}

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

C

题意

给定 \(N\) 个饭团，它们的长度升序排列，两个饭团能够组合当且仅当放在上面的饭团的长度的两倍小于等于下面的饭团长度。每个饭团可以使用无限次，求组合数量。

题解

在无限次使用条件下，由于已经升序排列，可以使用双指针维护对于左端点 \(L\) ，能满足它的最左边的右端点 \(R\) ，显然 \(R\) 及其之后的饭团都是可以满足条件的。使用二分查找也可。

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

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        auto it = lower_bound(A.begin(), A.end(), A[i] * 2) - A.begin();
        if (it == N) {
            break;
        }
        ans += (N - it);
    }
    cout << ans << "\n";
}

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

D

题意

\(N\) 个人依次长大，当一个人长大时，会从之前已经长大的人获得一个石头（如果没有就不会给），现在给定每个人初始的石头数，给出全部人长大后每个人的石头数。

题解

考虑到一个人长大后会依次给他之后的人发石头，那么石头不足以给后面的所有人发时，能获得石头的只有他之后连续的几个人。那么此时对于会获得石头的人，它们的石头数量其实就是区间里每个人都加 1 。由于从前到后每个人的石头数量可以依次确定下来，所以可以直接使用差分数组维护区间修改。

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;
    cin >> N;
    vector<int> A(N), B(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    for (int i = 0; i < N; i++) {
        if (i) {
            B[i] += B[i - 1];
        }
        A[i] += B[i];
        int k = min(A[i], N - i - 1);
        A[i] -= k;
        B[i + 1]++;
        B[i + k + 1]--;
        cout << A[i] << " \n"[i == N - 1];
    }
}

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

E

题意

给定 \(N\) 个饭团，它们的长度升序排列，两个饭团能够组合当且仅当放在上面的饭团的长度的两倍小于等于下面的饭团长度。每个饭团最多可以使用一次，求最大组合数量。

题解

在 C 题的基础上，多了最多使用一次的限制，那么容易想到应该贪心地让长度较小的饭团优先匹配，然而并不是直接进行二分查找，因为这样可能会让小饭团匹配到中等饭团，然而更大的两个饭团无法匹配上。

考虑到答案的上界为 \(\lfloor N/2\rfloor\)，我们可以从 \(R = \lfloor N/2\rfloor\) 开始为较小的饭团匹配，采用双指针的思想，一旦无法与左端点匹配上，就只移动右端点即可，因为在升序排列的条件下不会有更优的答案了。

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

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int ans = 0;
    int l = 0, r = N / 2;
    while (l < N / 2 && r < N) {
        if (A[l] * 2 <= A[r]) {
            ans++;
            l++;
        }
        r++;
    }
    cout << ans << "\n";
}

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