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

A - Supermajority#

直接判断是否 $A \times 3 > B \times 2$ 即可。

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

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

11
void solved() {
12
    int a, b;
13
    cin >> a >> b;
14
    if(a * 3 > b * 2) cout << "Yes" << endl;
15
    else cout << "No" << endl;
16
}
17

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

B - Parking 2#

我的方法可能相对复杂了，官方答案写循环来累加会更快一些。这里进行了分类讨论计算。先特判 $b \leq l$ 和 $a \geq r$ 的情况，这两种都是 $[a, b]$ 区间全部付 $Y$ ，然后根据 $l < b \geq r$ 和 $b > r$ 的情况分类讨论 $a$ ，然后确定具体的区间计算公式。

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

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

11
void solved() {
12
    int x, y, l, r, a, b;
13
    cin >> x >> y >> l >> r >> a >> b;
14
    if(b <= l || a >= r) cout << (b - a) * y << endl;
15
    else if(l < b && b <= r && a <= l) cout << (b - l) * x + (l - a) * y << endl;
16
    else if(l < b && b <= r && a > l) cout << (b - a) * x << endl;
17
    else if(b > r && a <= l) cout << (b - r + l  - a) * y + (r -l) * x << endl;
18
    else if(b > r && l < a < r) cout << (b - r) * y + (r - a) * x << endl;
19
}
20

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

C - Reverse Permutation#

这题我们用一个双端队列维护来反转状态。我们可以这样理解，进行一次翻转实际上只是翻转了前 $k$ 项，没有改变他们的相对位置，也就是说后续的操作不会影响它们的相对的位置，一反转就全部一起翻转了。所以对于一个位置 $i$ ，我们只需要考虑它当前应该放在队列前方还是后方，最后根据逆转状态判断，从头开始输出还是从尾开始输出答案即可。
这里的实现我们用一个 $re$ (初始为 $false$ 未翻转)来记录翻转状态，然后遍历 $n$ 次，每次都判断对应 $i$ 的字符串 $s[i - 1]$ 是否为 $'o'$ ，如果位 $'o'$ 就改变翻转状态 $re$ 。然后根据 $re$ 来判断是放队头还是队尾。最后输出结果时也需要根据 $re$ 决定从头开始输出还是从尾开始输出。

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

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

11
void solved() {
12
    int n; string s;
13
    cin >> n >> s;
14

15
    deque<int> a;
16
    bool re = false;
17
    for(int i = 1; i <= n;i++){
18
        if(s[i - 1] == 'x'){
19
            if(re) a.push_front(i);
20
            else a.push_back(i);
21
        }
22
        else{
23
            re = !re;
24
            if(re) a.push_back(i);
25
            else a.push_front(i);
26
        }
27
    }
28
    for(int i = 0; i < n;i++){
29
        int ans;
30
        if(re){
31
            ans = a.back();
32
            a.pop_back();
33
        }
34
        else{
35
            ans = a.front();
36
            a.pop_front();
37
        }
38
        cout << ans << " ";
39
    }
40
}
41

42
int main() {
43
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
44
    int _ = 1;
45
    //cin >> _;
46
    while (_--) {
47
        solved();
48
    }
49
    return 0;
50
}

D - X to Y#

这题我们需要将它理解为一个树的最短路问题。我们定义这个数的深度为 $[z]$ 的操作次数，节点的值为 $z$ 。因此这是一颗以 $0$ 为根节点的树，对于一个节点 $i$ ，父节点为 $u = [\frac{i}{k}]$ ，子节点 $v$ 为满足 $i = [\frac{v}{k}]$ 的所有 $v$ 。我们类比一下就可以知道题目说的两种操作就是向上跳（前往唯一的父节点）或者向下跳（前往任意的子节点）。所以对于题目给定的 $X$ 和 $Y$ ，求 $X$ 变成 $Y$ 需要多少次操作，其意就是给定了两个树的节点，求它们之间最短路的距离。
这里我们可以不需要去真的建图来做，我们可以只模拟一下这个跳一跳的过程。我们让 $X$ 和 $Y$ 都分别向上跳， $X$ 和 $Y$ 每跳一步都让步数 $ans$ 计数加一，然后一直跳到它们有相同的深度。接着让 $X$ 和 $Y$ 同步向上跳，（ $x$ 和 $Y$ 都跳了一步， $ans$ 加二）直到它们最终相等，（到达连通点），最后输出 $ans$ 即可。

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

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

11
void solved() {
12
    ll x, y, k;
13
    cin >> x >> y >> k;
14

15
    auto depth = [&](ll val) {
16
        ll d = 0;
17
        while(val){
18
            val /= k;
19
            d++;
20
        }
21
        return d;
22
    };
23
    ll dx = depth(x), dy = depth(y);
24
    ll ans = 0;
25
    while(dx > dy){
26
        x /= k;
27
        dx--;
28
        ans++;
29
    }
30
    while(dy > dx){
31
        y /= k;
32
        dy--;
33
        ans++;
34
    }
35
    while(x != y){
36
        x /= k;
37
        y /= k;
38
        ans += 2;
39
    }
40
    cout << ans << endl;
41
}
42

43
int main() {
44
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
45
    int _ = 1;
46
    cin >> _;
47
    while (_--) {
48
        solved();
49
    }
50
    return 0;
51
}

Mkrari的个人博客

A - Supermajority#

B - Parking 2#

C - Reverse Permutation#

D - X to Y#