Mkrari

GitHub

统计加载中...

公告

欢迎访问我的博客！这里会分享技术文章和生活感悟。

Mkrari

GitHub

统计加载中...

公告

欢迎访问我的博客！这里会分享技术文章和生活感悟。

标签

ACM CTF 教程新生赛杂谈

744 字

2 分钟

Atcoder_Beginner_Contest_458(A~D题)

2026-05-16

ACM

统计加载中...

这期 $abc$ 跨度巨大，后面 $E-F$ 题的 $NTT$ 和 $AC$ 自动机超出我目前的水平了，所以就不补了。
题目链接：https://atcoder.jp/contests/abc458/tasks

A - Chompers#

只输出字符串中间的答案部分即可。

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<int, int> pii;
8

9
void solved() {
10
    string s;
11
    int n;
12
    cin >> s >> n;
13
    for (int i = 0; i < s.size(); i++){
14
        if(i >= n && i < (int)s.size() - n){
15
            cout << s[i];
16
        }
17
    }
18
}
19

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

B - Count Adjacent Cells#

我们先让数组的值初始化为全 $1$ ，然后每次通过方向数组累加周围四格的值就是答案了。

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<int, int> pii;
8

9
int a[60][60];
10
int tx[5] = {0, 0, 0, 1, -1};
11
int ty[5] = {0, 1, -1, 0, 0};
12

13
void solved() {
14
    int n, m;
15
    cin >> n >> m;
16
    memset(a, 1, sizeof(a));
17
    for(int i = 1; i <= n;i++)
18
        for(int j = 1; j <= m;j++)
19
            a[i][j] = 1;
20
    for(int i = 1; i <= n;i++){
21
        for (int j = 1; j <= m;j++){
22
            int cnt = 0;
23
            for(int k = 1; k <= 4;k++){
24
                int x = i + tx[k];
25
                int y = j + ty[k];
26
                if(a[x][y] == 1){
27
                    cnt++;
28
                }
29
            }
30
            cout << cnt << " ";
31
        }
32
        cout << endl;
33
    }
34
}
35

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

C - C Stands for Center#

这题我们先记录下所有 $C$ 的字符的位置，思路是每次我们都以当前的 $C$ 字符的位置为中心，左右分别取一个字符。如果可以取到， $cnt$ 就加一，然后继续左右分别取一个，只要左右有一方取不到就停。这里我们直接取左右端离中心 $C$ 距离较小的一段直接计入 $cnt$ 即可。如果没有 $C$ 字符出现就输出 $0$ 。

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<int, int> pii;
8

9
void solved() {
10
    vector<int> pos;
11
    string s;
12
    cin >> s;
13
    for(int i = 0; i < (int)s.size();i++){
14
        if(s[i] == 'C'){
15
            pos.push_back(i);
16
        }
17
    }
18
    if(pos.size() == 0){
19
        cout << 0 << endl;
20
        return;
21
    }
22
    ll cnt = (int)pos.size();
23
    for(auto it : pos){
24
        it++;
25
        cnt += min(it - 1, (int)s.size() - it);
26
    }
27
    cout << cnt << endl;
28
}
29

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

D - Chalkboard#

这题我们看到需要在每次查询都输出这个不断更新的序列的中位数。但这里要注意的是，如果我们每次都进行遍历操作的话就会超时。所以我们需要优化我们的思路。
这里其实很容易想到使用优先队列进行快速排序的操作来方便我们查询。但问题是优先队列只能看到队顶的元素，并且也只能操作队顶。看起来似乎是无法查找中位数的。不过我们可以利用一个双堆来查找中位数。
我们开一个最大堆和最小堆，它们的堆顶分别是堆里的最大值和最小值。现在我们让最大堆里面整个序列的偏小的下半部分，最小堆里面是偏大的上半部分。那么我们就可以让最大堆和最小堆的堆顶分别存放中间的两个数了。如果是偶数的话我们就取两边堆顶的值除以 $2$ 。奇数时我们就取元素更多的那一边的堆顶即可。
现在我们看如何构造这样的两个堆。我们先将一个元素压入最大堆，然后再弹出最大堆的堆顶，将它加到最小堆里。此时如果最大堆的元素个数小于了最小堆里的元素个数，我们就重新将它移回最大堆。我们不难发现，这样的操作每次都将相对较大的数放进了最小堆，把较小的数留在了最大堆，从而可以保证每次中位数都在堆顶，从而满足要求。
这题每次查询时都是压入堆中的序列和都是奇数，所以根据我们的构造，每次查询时输出最大堆的堆顶就是中位数了。

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<int, int> pii;
8

9
priority_queue<int, vector<int>, greater<int>> min_pq;
10
priority_queue<int> max_pq;
11

12
void add(int x){
13
    max_pq.push(x);
14
    min_pq.push(max_pq.top());
15
    max_pq.pop();
16
    if(max_pq.size() < min_pq.size()){
17
        max_pq.push(min_pq.top());
18
        min_pq.pop();
19
    }
20
}
21

22
void solved() {
23
    int x, q;
24
    cin >> x >> q;
25
    max_pq.push(x);
26
    while(q--){
27
        int a, b;
28
        cin >> a >> b;
29
        add(a), add(b);
30
        cout << max_pq.top() << endl;
31
    }
32
}
33

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