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

A - Secret Numbers#

新建一个字符串 $t$ 拼接遍历 $s$ 找出的数字字符输出即可。

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
    string s, t = "";
12
    cin >> s;
13
    for (auto it : s){
14
        if(it >= '0' && it <= '9'){
15
            t += it;
16
        }
17
    }
18
    cout << t << 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
}

B - Gift#

我们用一个二维数组记录对应第 $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
vector<vector<int>> a;
11

12
void solved(){
13
    int n;
14
    cin >> n;
15
    a.resize(n + 1);
16
    for(int i = 1; i <= n;i++){
17
        int x;
18
        cin >> x;
19
        while(x--){
20
            int y;
21
            cin >> y;
22
            a[y].push_back(i);
23
        }
24
    }
25
    int cnt = 1;
26
    for(auto it : a){
27
        if(cnt == 1) {cnt++;continue;}
28
        if(it.empty()) cout << 0 << " ";
29
        else cout << it.size() << " ";
30
        for(auto it2 : it){
31
            cout << it2 << " ";
32
        }
33
        cout << endl;
34
    }
35
}
36

37
int main() {
38
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
39
    int _ = 1;
40
    // cin >> _;
41
    while(_--){
42
        solved();
43
    }
44
    return 0;
45
}

C - Not Covered Points#

这题的关键点是我们要找到一个合适的遍历方法去判断当前的点是否满足条件。题意简单来说就是对于两个 $1$ 到 $N$ 的排列序列对 $(x, y)$ 。保证对于一个 $(x_i, y_i)$ ，原点， $x$ 轴和 $y$ 轴围起来的矩阵内(不包含边界)不能有其他点，记录有多少个这样的点。我的思路是 $x$ 从 $1$ 开始，判断 $y$ 是否小于等于前面的最小 $y$ 坐标( $miny$ )，如果满足就说明满足条件， $ans$ 加一。我们可以这样理解，我们现在已经给定了 $y$ 轴为矩阵的左边， $y$ 轴为矩阵的下边，现在对于每一个矩阵，我们再给定 $x = i$ 这个右边，如果想要满足条件我们就需要 $y = j$ 这个上边不上升(可以递减或者不变)，这样我们每一个矩阵的右上端点 $(x_j, y_j)$ 划定的矩阵内就都不包含前面一个矩阵的右上端点 $(x_i, y_i)$ 了。
如果出现了比目前最小的 $miny$ 要大的 $y$ ，则这个坐标不满条件，不计数。后续如果还有满足小于 $miny$ 的 $y$ 就继续计数，然后更新 $miny$ 即可。

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 a[300010];  //记录对应x = i时，y的值。
11

12
void solved(){
13
    int n;
14
    ll ans = 0;
15
    cin >> n;
16
    for(int i = 1; i <= n;i++){
17
        int x, y;
18
        cin >> x >> y;
19
        a[x] = y;
20
    }
21
    //记录目前出现的最小值。
22
    int miny = n + 1;
23
    for(int i = 1; i <= n;i++){
24
        if(a[i] < miny){  //因为是排列，不用考虑相等的情况
25
            ans++;
26
            miny = a[i];
27
        }
28
    }
29
    cout << ans << endl;
30
}
31

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

D - Accomplice#

我们先对有效区间进行化简，对于一个嫌疑人 $i$ 它真正能作案的时间为 $[S_i, T_i - D]$ ，同理另一个嫌疑人 $j$ 。那么对于这两个人真正能作案的时间就是 $[max(S_i, S_j), min(T_i - D, T_j - D)]$ ，所以对于这个时间段内的时刻都是可以作案的时间。但如果我们每次都两两判断的话就会超时。（复杂度 $O(N^2)$ ，而 $n$ 为 $2 \times 10^5$ ）所以我们需要换种思路。
这里我们可以通过对时刻进行遍历判断累计作案的人。我们可以这样想，假设对于每一个时刻能作案的有 $k$ 个人，那么我们能该时刻能实现共同作案的就是 $C^{2}_{k}$ 种情况。我们只需要遍历一次所有时刻 $[1, 1 \times 10^6]$ 即可，这种做法的时间复杂度为 $O(N)$ ，完全可行。而对于对应时刻内的可作案人数，我们可以通过对每一个嫌疑人对应的可作案时间区间做差分来优化即可。

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, D;
12
    ll ans = 0;
13
    cin >> N >> D;
14
    vector<int> diff(1000010, 0);
15
    for(int i = 1; i <= N; i++){
16
        int S, T;
17
        cin >> S >> T;
18
        int laststart = T - D;
19
        if(S <= laststart){
20
            diff[S]++;
21
            diff[laststart + 1]--;
22
        }
23
    }
24
    ll person = 0;
25
    for(int x = 1; x <= 1000000; x++){
26
        person += diff[x];
27
        ans += person * (person - 1) / 2;
28
    }
29
    cout << ans << endl;
30
}
31

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

E - Alternating Costs#

这题算是一个贪心的数学思维题。根据题意，左右横着走或者上下竖着走的代价是一样的，所以我们计算代价最小可以不考虑正负，直接取绝对值。然后我们可以通过自己手动模拟发现斜着走一格有两种情况: $2 \times A$ 或 $2 \times B$ 。所以我们斜着走的情况的代价最小为 $2 \times min(A, B)$ 。然后对于左右横走两格，我们也有两种情况： $A + B$ 或者斜着走两次，也就是 $4 \times min(A, B)$ 。然后我们还要注意到一点，我们所需操作的次数和 $X + 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
//计算贡献
11
ll calc_even(ll x, ll y, ll A, ll B){
12
    ll cheap = min(A, B);
13
    ll diagonal = min(x, y);
14
    ll straight = abs(x - y) / 2;
15
    return diagonal * 2 * cheap
16
         + straight * min(A + B, 4 * cheap);
17
}
18

19
void solved(){
20
    ll A, B, X, Y;
21
    cin >> A >> B >> X >> Y;
22
    //取绝对值
23
    X = abs(X);
24
    Y = abs(Y);
25
    //操作数为偶数
26
    if((X + Y) % 2 == 0){
27
        cout << calc_even(X, Y, A, B) << endl;
28
        return;
29
    }
30
    //操作数为奇数
31
    ll ans = LLONG_MAX;
32
    ans = min(ans, A + calc_even(abs(X - 1), Y, A, B));
33
    ans = min(ans, A + calc_even(X + 1, Y, A, B));
34
    ans = min(ans, B + calc_even(X, abs(Y - 1), A, B));
35
    ans = min(ans, B + calc_even(X, Y + 1, A, B));
36
    cout << ans << endl;
37
}
38

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

Mkrari的个人博客

A - Secret Numbers#

B - Gift#

C - Not Covered Points#

D - Accomplice#

E - Alternating Costs#