JoeyDDong's Blog
AtCoder Beginner Contest 380 Summary
JoeyDDong
  2024-11-18   2025-01-04  2.2k Words  10 Mins

本文是 AtCoder Beginner Conteset（ABC）380 的总结笔记。

A - 123233

Problem：A - 123233

题目：

给定一个 6 位整数。判断这个整数内是否刚好出现了次 1,次 2,次 3。

思路：

按照字符串读入，直接排序，看结果和 122333 是否相同即可。

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
36
37
38
39
40
41
42
// Problem: https://atcoder.jp/contests/abc380/tasks/abc380_a

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

// 无脑写法
void solve1() {
    string s;
    cin >> s;
    int a = 0, b = 0, c = 0;
    for (auto x : s) {
        if (x == '1')
            a++;
        if (x == '2')
            b++;
        if (x == '3')
            c++;
    }

    if (a == 1 && b == 2 && c == 3)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

// 推荐写法：
void solve2() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    cout << (s == "122333" ? "Yes" : "No") << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    // solve1();  // 解法 1
    solve2();  // 解法 2
    return 0;
}

B - Hurdle Parsing

Problem：B - Hurdle Parsing

题目：

给定一个字符串，仅由 | 和 - 构成。输出两个 | 之间 - 的数量。

思路：

维护一个变量 now：

当遇到 - 时 now 自增计数；

当遇到 | 时保存 now 的值，并清零。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Problem: https://atcoder.jp/contests/abc380/tasks/abc380_b

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

// 双指针做法
void solve1() {
    string s;
    cin >> s;

    vector<int> res;
    int last = 0;
    for (int i = 1; i < s.size(); i++) {
        int j = i;
        while (j < s.size() && s[j] != '|')
            j++;
        res.push_back(j - last - 1);
        i = j;
        last = j;
    }

    for (auto x : res)
        cout << x << " ";
    cout << endl;
}

// 推荐写法：更具有编程思维
void solve2() {
    string s;
    cin >> s;

    vector<int> res;
    int now = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '|')
            res.push_back(now), now = 0;
        else
            now++;
    }

    for (int i = 1; i < res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    // solve1();
    solve2();
    return 0;
}

C - Move Segment

Problem：C - Move Segment

题目：

给定长度为的字符串，仅由 0 和 1 构成。

把第个 1 block 移动到第个 1 block 后面，重新输出字符串。

思路：

解法 1：

按照块来寻找。每次找到当前 1 block 的起点 st 和终点 ed，同时保存上一个 1 block 的起点 last_st 和终点 last_ed。数到第个 1 block 的时候，使用 substr 将字符串重新拼接输出即可。

image-20241211220621241

解法 2：

将原字符串整理到一个 vector<PII> 中。每个 PII 元素同时保存了出现的字符 和 出现的次数。

只需将第次出现 1 和他前面的元素交换位置，重新输出即可。

image-20241211221437203
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Problem: https://atcoder.jp/contests/abc380/tasks/abc380_c

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

// 解法 1：使用字符串拼接
void solve1() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    string res;

    int last_start = 0, last_ed = 0;
    int start = 0, ed = 0;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        int j = i;
        // 找第一次 1 出现的起点
        while (j < s.size() && s[j] != '1')
            j++;
        start = j;

        // 找 1 出现的终点
        while (j < s.size() && s[j] == '1')
            j++;
        ed = j - 1;

        if (cnt == 0) {
            last_start = start, last_ed = ed;
        }

        cnt++;

        if (cnt == k) {
            res = s.substr(0, last_ed + 1) + s.substr(start, ed - start + 1) +
                  s.substr(last_ed + 1, start - last_ed - 1) + s.substr(ed + 1);
            break;
        }
        i = j - 1;
        if (cnt > 1) {
            last_start = start, last_ed = ed;
        }
    }

    cout << res << endl;
}

// 解法 2：
void solve2() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    s += ".";  // 技巧：防止越界，保证最后一段也被记录
    vector<PII> v;
    int now = s[0], num = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == now)
            num++;  // 计算段内长度
        else {
            v.push_back({now - '0', num});  // 记录这一段的数据:{符号，长度}
            now = s[i], num = 1;
        }
    }

    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        // 找到第 k 段为 1 的位置
        if (v[i].first == 1) {
            cnt++;
            if (cnt == k)
                // 交换位置
                swap(v[i], v[i - 1]);
        }
    }

    // 重新输出
    for (auto x : v) {
        for (int i = 0; i < x.second; i++)
            cout << x.first;
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    // solve1();
    solve2();
    return 0;
}

D - Strange Mirroring

Problem：D - Strange Mirroring

递归

题目：

给定一个字符串，包含大小写字母。

对执行下面操作次。

创建字符串，是将中的大小写颠倒。然后将接到后面。

进行次查询：返回的第个字母。

约束条件：

is a string consisting of uppercase and lowercase English letters, with length betweenand, inclusive.

andare integers.

思路：

这道题思路很抽象。如下图，以 aBd 为例。

可以发现经过次操作后，字符串总长度变为了。

对于查询位置 x 的字符，我们总是能够找到 x 前面距离最近的，计算出与他的距离 L，我们就能推导出它在上一步操作中的位置。以此为递归的依据，最终能够找到它在原始字符串中的位置。

根据记录的跳转次数：

如果是奇数次，则发生大小写转换；

如果是偶数次，则保持原样。

因此，对于任意大的数字，都可以在的时间复杂度内完成单次查询。

完成次查询总时间复杂度为。

image-20241211235448096

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Problem: https://atcoder.jp/contests/abc380/tasks/abc380_d

// 这是一道非常典型的递归题目
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

string s;
int t;

// 大小写转换
// ascii 码中：A 为65，a 为 97，相差 32
char change(char ch) {
    return ch >= 'a' ? (ch - 32) : (ch + 32);
}

// 递归
char f(LL x, bool is_reverse) {
    // 如果已经到了最前面
    if (x <= s.size()) {
        // 如果需要翻转
        if (is_reverse)
            return change(s[x - 1]);
        // 不需要翻转
        else
            return s[x - 1];
    }

    LL k = s.size();
    // 找到距离 x 左边最近的倍数
    while (k * 2 < x)
        k *= 2;
    // 减去这个长度，向前找
    return f(x - k, !is_reverse);
}

void solve() {
    cin >> s >> t;
    while (t--) {
        LL x;
        cin >> x;
        cout << f(x, false) << " ";
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

E - 1D Bucket Tool

Problem：E - 1D Bucket Tool

并查集处理区间染色问题。

题目：

有编号的个格子排成一行。每个格子的初始颜色为。

给定次查询，查询有下面两种情况：

1 x c ：把 x 能到达的所有格子都涂成 c 颜色。

2 c：打印颜色为 c 的格子的数量。

约束条件：

……

思路：

使用并查集来处理区间染色问题。

并查集在记录连通块的同时，还要维护额外的三个数组值：

  • 区间的左端点 l

  • 区间的右端点 r

  • 集合内部的节点数 cnt

详细参照下面代码：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Problem: https://atcoder.jp/contests/abc380/tasks/abc380_e

// 使用并查集处理区间染色问题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6 + 10;

// 节点的父节点，每个集合的节点数，集合的最左端点，集合的最右端点
int fa[N], cnt[N], l[N], r[N];
int color[N];      // 节点 i 的颜色
int color_cnt[N];  // 颜色 i 的数量
int n, q;

// 查找节点 x 所属的集合
int _find(int x) {
    // 如果 x 是根节点，就返回 x
    // 如果不是，就继续找祖宗。同时进行路径压缩
    return x == fa[x] ? x : fa[x] = _find(fa[x]);
}

// 将 x 所在集合涂成颜色 c
void paint(int x, int c) {
    x = _find(x);                   // 找 x 的祖宗
    color_cnt[color[x]] -= cnt[x];  // 从原来的颜色计数中减去整个集合的大小
    color[x] = c;                   // 染色
    color_cnt[c] += cnt[x];  // 新颜色计数中添加整个集合大小
}

// 合并两个集合
void _union(int x, int y) {
    int fx = _find(x), fy = _find(y);  // 找到两个节点的祖宗节点
    fa[fx] = fy;                       // fx 的祖宗改为 fy
    l[fy] = min(l[fx], l[fy]);         // 更新合并后集合的左边界
    r[fy] = max(r[fx], r[fy]);         // 更新合并后集合的右边界
    cnt[fy] += cnt[fx];                // 更新合并后集合的节点数量
}

void solve() {
    // 读入数据
    cin >> n >> q;
    // 将每个节点
    for (int i = 1; i <= n; i++) {
        // 初始化：每个节点的颜色，父节点，左边界，右边界
        color[i] = fa[i] = l[i] = r[i] = i;
        cnt[i] = 1;  // 初始化：每个集合计数，只有一个节点
        color_cnt[i] = 1;  // 初始化：每种颜色只有一个节点
    }

    while (q--) {
        int op;
        cin >> op;
        // 操作 1：染色操作
        if (op == 1) {
            int x, c;
            cin >> x >> c;  // 读入要染色的节点和 x 和目标颜色 c
            paint(x, c);    // 染色

            // 检查并合并相邻的同色集合
            int L = l[_find(x)], R = r[_find(x)];
            // 如果左边相邻集合同色
            if (color[_find(L - 1)] == c)
                _union(L - 1, x);
            // 如果右边相邻集合同色
            if (color[_find(R + 1)] == c)
                _union(R + 1, x);
        }
        // 操作 2：查询操作
        else {
            int c;
            cin >> c;
            cout << color_cnt[c] << endl;
        }
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
AtCoder Beginner Contest 380 Summary
2024/blog/4952/
Author
JoeyDDong
Published
2024-11-18 22:10
License
  1. A - 123233
    1. 题目：
    2. 思路：
  2. B - Hurdle Parsing
    1. 题目：
    2. 思路：
  3. C - Move Segment
    1. 题目：
    2. 思路：
      1. 解法 1：
      2. 解法 2：
  4. D - Strange Mirroring
    1. 题目：
    2. 约束条件：
    3. 思路：
  5. E - 1D Bucket Tool
    1. 题目：
    2. 约束条件：
    3. 思路：
  1. A - 123233
    1. 题目：
    2. 思路：
  2. B - Hurdle Parsing
    1. 题目：
    2. 思路：
  3. C - Move Segment
    1. 题目：
    2. 思路：
      1. 解法 1：
      2. 解法 2：
  4. D - Strange Mirroring
    1. 题目：
    2. 约束条件：
    3. 思路：
  5. E - 1D Bucket Tool
    1. 题目：
    2. 约束条件：
    3. 思路：