题目链接：https://atcoder.jp/contests/abc463/tasks

A - 16:9#

直接判断是否 $9 \times X = 16 \times Y$ 即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
void solved() {
11
    int x, y;
12
    cin >> x >> y;
13
    cout << ((9 * x == 16 * y) ? "Yes" : "No") << endl;
14
}
15

16
int main() {
17
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
18
    int _ = 1;
19
    //cin >> _;
20
    while (_--) {
21
        solved();
22
    }
23
    return 0;
24
}

B - Train Reservation#

直接遍历字符串数组判断对应的 $X -'A'$ 下标是否为 $o$ ，是就将 $has\_seat$ 标记为真然后输出 $Yes$ 即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
void solved() {
11
    int N; char X;
12
    cin >> N >> X;
13
    vector<string> S(N + 1);
14
    for(int i = 1; i <= N;i++) cin >> S[i];
15
    bool has_seat = false;
16
    for(int i = 1; i <= N;i++){
17
        if(S[i][X - 'A'] == 'o') has_seat = true;
18
    }
19
    cout << ((has_seat) ? "Yes" : "No") << endl;
20
}
21

22
int main() {
23
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
24
    int _ = 1;
25
    //cin >> _;
26
    while (_--) {
27
        solved();
28
    }
29
    return 0;
30
}

C - Tallest at the Moment#

这题的数据大小限制我们查询时只能用一次 $O(logN)$ 级别的查找。同时 $L$ 数组根据题目条件可知保证不降序，我们可以二分找到第一个大于 $T_i$ 的 $L_i$ 下标，（ $T_i$ 为整数，所以大于等于 $T_i + \frac{1}{2}$ 只能是后面的 $L$ 下标）然后输出对应要查询的下标的答案。这个答案我们可以通过倒序遍历 $H$ 数组，对于每个 $i$ 不断更新最大值，然后存入 $suffix\_max_i$ 来得到。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
int H[300010];
11
int L[300010];
12
int suffix_max[300010];
13

14
void solved() {
15
    int N, Q; cin >> N;
16
    for (int i = 1; i <= N;i++){
17
        cin >> H[i] >> L[i];
18
    }
19
    suffix_max[N] = H[N];
20
    for(int i = N - 1; i >= 1; i--){
21
        suffix_max[i] = max(suffix_max[i + 1], H[i]);
22
    }
23
    cin >> Q;
24
    while(Q--){
25
        int T; cin >> T;
26
        int pos = upper_bound(L + 1, L + 1 + N, T) - L;
27
        cout << suffix_max[pos] << endl;
28
    }
29
}
30

31
int main() {
32
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
33
    int _ = 1;
34
    //cin >> _;
35
    while (_--) {
36
        solved();
37
    }
38
    return 0;
39
}

D - Maximize the Gap#

这题我们先要深入理解一下题意。它要我们找互不覆盖的两块布上两个点的最小值，其实这个最小值就是在这两块布中，相对靠前的那块的右端点和相对靠后的左端点之间的距离。然后在能选出的 $K$ 个互不覆盖的布的前提下，找到这个距离最小能达到的最大值。所以我们根据题意，这个距离最小只会在所有满足相邻且互不覆盖的两个布之间出现。我们就在这些布里面找出最大值即可。
这题的思路依旧是二分，我们对于一个给定的距离最大值 $distance$ ，判断它是否满足 $k$ 个布的距离都大于等于 $distance$ 这个条件，满足就继续找更大的 $distance$ ，否则就找更小的 $distance$ 。对于这个条件的判断我们在 $check$ 中的用到了一种区间调度贪心的思想：
也就是选择结束时间较早(右端点较小)的区间，跳过重叠的区间，找到不重叠的区间的左端点再进行判断。这种方法可以保证避免选择到重叠的区间，同时不遗漏可能的答案，做出局部且全局最优的选择。
这里具体的实现就是按右端点从小到大排序，然后在遍历循环判断时检查后区间的左端点是否和前区间的右端点距离大于等于 $distance$ 。满足条件才会更新 $last\_right$ 和 $cnt$ 。
整体复杂度为排序加上二分内嵌遍历： $O(NlogN + Nlog10^9)$ ，可以通过本题。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<ll, ll> pll;
8
typedef pair<int, int> pii;
9

10
void solved() {
11
    int n, k;
12
    cin >> n >> k;
13
    vector<pii> cloth(n);
14
    for(int i = 0; i < n;i++){
15
        int L, R;
16
        cin >> L >> R;
17
        cloth[i] = {R, L};
18
    }
19
    //按右端点从小到大排序
20
    sort(cloth.begin(), cloth.end());
21
    //判断对于一个给定的距离，是否存在k个布能满足。
22
    auto check = [&](int distance) -> bool {
23
        int cnt = 0;
24
        ll last_right = -(1LL << 60);//让第一个右端点一定能初始化
25
        for(auto [R, L] : cloth){
26
            if(L >= last_right + distance){
27
                cnt++;
28
                last_right = R;
29
                if(cnt >= k) return true;
30
            }
31
        }
32
        return false;
33
    };
34
    //查找可能满足的最小得分的最大值，尽可能向右(大)搜
35
    int left = 1, right = 1e9, ans = -1;
36
    while(left <= right){
37
        int mid = left + (right - left) / 2;
38
        if(check(mid)){
39
            ans = mid;
40
            left = mid + 1;
41
        }
42
        else{
43
            right = mid - 1;
44
        }
45
    }
46
    cout << ans << endl;
47
}
48

49
int main() {
50
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
51
    int _ = 1;
52
    //cin >> _;
53
    while (_--) {
54
        solved();
55
    }
56
    return 0;
57
}

Mkrari的个人博客

A - 16:9#

B - Train Reservation#

C - Tallest at the Moment#

D - Maximize the Gap#