JoeyDDong's Blog
AtCoder Beginner Contest 386 Summary
JoeyDDong
  2025-01-02   2025-01-18  3.1k Words  13 Mins

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

A - Full House 2

Problem：A - Full House 2

模拟

有 ABCD 写着数字的四张牌。问能否添加一张牌，使得五张牌构成：3 张 x 和 2 张 y 的形式。

思路非常简单。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_a

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

int a[4];
map<int, int> h;

void solve() {
    // 读入四个数，同时计数
    for (int i = 0; i < 4; i++) {
        cin >> a[i];
        h[a[i]]++;
    }

    // 排序一下
    sort(a, a + 4);

    // 我们只看第一个数和最后一个数即可
    // 只能是 22 或者 13 或者 31 的形式，才能构成题目需要的形式
    if ((h[a[0]] == 2 && h[a[3]] == 2) || (h[a[0]] == 3 && h[a[3]] == 1) ||
        (h[a[0]] == 1 && h[a[3]] == 3))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

B - Calculator

Problem：B - Calculator

模拟

这道题目其实很暴力。只需要将所有的 00 转换成一个不相关的字符，最后看一下总长度就知道需要按多少次按键了。

本答案是将所有的 00 都转化为 1。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_b

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

string s;

void solve() {
    cin >> s;

    // 把所有的 00 转化为 1
    while (s.find("00") != s.npos)
        s.replace(s.find("00"), 2, "1");

    // 输出答案
    cout << s.size() << endl;
}

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

C - Operate 1

Problem：C - Operate 1

模拟

题目：

有三种操作：

  • 给 S 中添加任意一个字符
  • 删除 S 中的任意一个字符
  • 选择 S 中的任意一个字符并转化为另一个字符

请判断执行次操作中，是否能将 S 转化为 T

约束条件：

字符串最大长度

思路：

本题目是 F 题在情况下的特例。

分成三种情况来讨论：

  • case1：S 与 T 长度相同

  • case2：S 比 T 长度短 1

  • case3：S 比 T 长度长 1

case1 处理方法：

​ 找到正向和反向的最后一个差异点，如果位置相同，说明只有一个差异点

case2 和 case3 处理方法：

​ 只看长的那个字符串。找到第一个差异点，判断一下去掉这个差异点的字符串s 和 t 是否相同即可。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_c

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

string s, t;
int k;

void solve() {
    // 读入数据
    cin >> k >> s >> t;

    // 如果 s 和 t 完全相同
    if (s == t) {
        cout << "Yes" << endl;
        return;
    }

    // 情况 1：如果长度相同
    if (s.size() == t.size()) {
        int x, y;
        // 从前到后，找到最后一个差异点位置
        for (int i = 0; i < s.size(); i++)
            if (s[i] != t[i])
                x = i;
        // 从后往前，找到第一个差异点位置
        for (int i = s.size() - 1; i >= 0; i--)
            if (s[i] != t[i])
                y = i;
        // 如果位置相同，说明只有一个点不同
        if (x == y)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        return;
    }

    // 如果长度不同，让 s 是长的那个
    if (s.size() < t.size())
        swap(s, t);

    // 如果长度差异为 1
    if (s.size() - t.size() == 1) {
        int x;
        // 找到第一个差异点
        for (int i = 0; i < s.size(); i++)
            if (s[i] != t[i]) {
                x = i;
                break;
            }

        // 跳过这一个差异点，把前面和后面拼接起来
        string tmp = s.substr(0, x) + s.substr(x + 1);

        // 如果拼接后的字符串 tmp 和 t 相同，说明只有一个差异点
        if (tmp == t)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        return;
    }

    // 如果能走到这一步，说明长度差异大于 2
    cout << "No" << endl;
}

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

D - Diagonal Separation

Problem：D - Diagonal Separation

贪心

题目：

给定一个的网格，希望能按照下面条件将格子涂成黑色或白色：

  • 对于每一行：左边的格子都是黑色，右边的格子都是白色
  • 对于每一列：上面的格子都是黑色，下面的格子都是白色

已经给定了个格子的颜色，请问是否可以将剩余的个格子涂色，以满足上面条件。

约束条件：

思路：

如果所有的点都是合法的，我们可以很容易的发现单调性：

从上往下，最左侧的白色格子出现的位置 min_y 一定是逐渐减小的。

每一行中，一旦要是有任何一个黑色格子的 y 坐标大于 min_y ，就一定不能满足题目的约束条件。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_d

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

const int N = 2e5 + 10;

int n, m;
struct Node {
    int x, y;
    char c;
} p[N];

bool cmp(const Node& a, const Node& b) {
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void solve() {
    // 读入数据
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> p[i].x >> p[i].y >> p[i].c;

    // 让格子升序排列
    sort(p, p + m, cmp);

    // min_y 初始化
    int min_y = 1e9 + 10;
    // 遍历所有的格子
    for (int i = 0; i < m; i++) {
        // 如果是白色：维护min_y，即白色出现在最左侧的位置
        if (p[i].c == 'W')
            min_y = min(min_y, p[i].y);
        // 如果是黑色格子，并且 y 值超过了 min_y，说明条件不成立
        else if (p[i].y >= min_y) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

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

E - Maximize XOR

Problem：E - Maximize XOR

DFS + 优化

题目：

给定一个长度为的非负整数序列，整数。

保证组合数

从中选择个不同的元素，求他们值的最大值。

备注：

：相异为，相同为。例如：

约束条件：

思路：

这道题目直接使用 DFS 搜索。但是需要两处前置知识：

前置知识 1：XOR 的性质

XOR 有一些重要的性质：

  1. 可逆性：如果，那么，也就是说再次 XOR 同一个数就相当于把它 “消去”
  2. 自我抵消：任何数字和他本身做 XOR，结果都是0，即
  3. 恒等性：热河数字 a 和 0 做 XOR，结果不变，即

从上面的性质，可以推出本题中用到的结论：

假设长度为 N 的数列，取出了前 K 个元素做 XOR 运算。

等价于先把所有元素做 XOR 运算，再和没有取出的 N-K 个元素做 XOR 运算。

前置知识 2：组合数的性质

组合数有一个重要的性质：

显然，从 n 个物品里面选 m 个组成的方案数，和从 n 个物品中选 n-m 个丢掉的方案数是一致的。

本题思路：

根据上述的两条性质，我们可以对 DFS 进行优化：

  • 如果k的值比较小，我们就搜即可
  • 如果 k 的值比较大，我们就搜，但是前提要先将所有数组 a 的值进行一遍 XOR 运算。

为什么要使用这个优化方法呢？

本题中的递归函数 dfs，每调用一次我可以视为的时间复杂度。当 k 很大的时候，递归函数总的调用次数为次，尽管的值可能并不大，但是的值会非常的大。

举例：尽管 $C^{98}{100} = 4950 < 10^{6}，但是中间值C^{50}{100} = 10^{29}$ 非常的巨大，显然超出了限定的时间复杂度。

所以使用这个优化方法可以极大的减少时间复杂度。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_e

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

const int N = 2e5 + 10;

LL res;
LL a[N];
int n, k;

void dfs(int x, LL sum, int n, int k) {
    // 搜到底了
    if (k == 0) {
        res = max(res, sum);
        return;
    }
    // 超出范围了
    if (x == n + 1)
        return;

    // 选中当前值
    dfs(x + 1, sum ^ a[x], n, k - 1);
    // 不选当前值
    dfs(x + 1, sum, n, k);
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    LL sum = 0;
    // 如果 k 比较大，C(k,n)比较难算，我们就算C(n-k,n)
    if (k > n / 2) {
        k = n - k;
        for (int i = 1; i <= n; i++)
            sum ^= a[i];
    }

    // dfs
    dfs(1, sum, n, k);

    // 输出结果
    cout << res << endl;
}

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

F - Operate K

Problem：F - Operate K

最短编辑距离 + 带状 DP

题目：

有三种操作：

  • 给 S 中添加任意一个字符
  • 删除 S 中的任意一个字符
  • 选择 S 中的任意一个字符并转化为另一个字符

请判断执行次操作中，是否能将 S 转化为 T

约束条件：

字符串最大长度

思路：

本题是 C 的加强版。

直观上，这是一道“最短编辑距离”问题。

前置知识：“最短编辑距离”问题的标准做法：

这类问题有一个标准的 DP 做法如下：

令表示字符串的前个字符变成的前字符所需要的最短编辑距离。

初始状态，那么 i 和 j 的双重循环下，状态迁移公式为：

其中：

  • ：表示删除 S 的一个字符
  • ：表示给 S 插入一个字符（或者说给 T 删去一个字符）
  • ：表示“替换”或“匹配”。如果，则无需替换，；否则

总时间复杂度为：

本题的优化思路：带状区域计算 DP

如果按照标准做法，那本题的时间复杂度是，显然会 TLE。

但是本题规定了最大操作数不超过（不超过 20 次操作），这个约束条件就带来了优化空间。

即：只对“有希望编辑距离不超过” 的位置进行 DP 计算。其他位置将会直接认为距离非常大（用 ∞ 表示），从而剪枝掉大量不必要的计算。

如何做？

在计算的时候，如果的差距很大，意味着比短或长很多。如果要将变得和完全相同，则操作次数至少要大于。此时就可以将超过的区域直接视为 +∞，不再计算。

具体做法：

  • 只让在的范围内活动
  • 超出范围的直接置为 +∞

这样就将原本的时间复杂度压缩到

注意点：

习惯上可能直接就把 f 数组声明为大小。但是本题中最大为 5e5，此时开出的数组空间为：5e5 * 5e5 * sizeof(int) 大小的内存。对于 int 类型（假设为 4 字节大小），这个数组将会消耗 1e12 byte = 1000GB 的空间，显然是不现实的。如果直接声明这么大的数组，会报 bus error 错误。

而且我们实际上只使用了中间很小的一部分，绝大多数的空间都是用不上的。所以使用偏置换算的方法即可。

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
// Problem: https://atcoder.jp/contests/abc386/tasks/abc386_f

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

const int N = 5e5 + 10;

string S, T;
int K;
int f[N][60];

int get_dp(int i, int j) {
    if (abs(i - j) > K)
        return 0x3f3f3f3f;
    // 偏置
    return f[i][j - i + 30];
}

void solve() {
    cin >> K >> S >> T;
    int slen = S.size(), tlen = T.size();

    S = " " + S;
    T = " " + T;

    // f 数组初始化为正无穷
    memset(f, 0x3f, sizeof f);

    /* 设置初始边界 */
    // 对应原来的 f[0][0]：即将空串转化为空串需要 0 步操作
    f[0][30] = 0;
    // 将空串变成长度为 i 的串，需要 i 步插入操作
    for (int i = 1; i <= K; i++)
        f[0][30 + i] = i;
    // 将长度为 i 的串变成空串，需要 i 步删除操作
    for (int i = 1; i <= K; i++)
        f[i][30 - i] = i;

    /* DP */
    // 遍历 S 的每一位
    for (int i = 1; i <= slen; i++) {
        // 遍历偏置
        for (int x = 0; x < 60; x++) {
            // 还原出真正的 j
            /*
                原理：j 只能在[i-30,i+30]范围内，所以下界 j>=i-30
                这里加入了偏置 x 去掉了等号
                即 j = i - 30 + x
            */
            int j = i - 30 + x;
            // 如果 j 超出了范围
            if (j <= 0 || j > tlen)
                continue;

            int cur_dp = 0x3f3f3f3f;
            // S 删除一个字符
            cur_dp = min(cur_dp, get_dp(i - 1, j) + 1);
            // S 添加一个字符（即，T 删除一个字符）
            cur_dp = min(cur_dp, get_dp(i, j - 1) + 1);

            int c = 1;
            if (S[i] == T[j])
                c = 0;
            // S 替换一个字符 或者 不操作
            cur_dp = min(cur_dp, get_dp(i - 1, j - 1) + c);
            // 更新 f
            f[i][x] = cur_dp;
        }
    }

    // 输出结果
    if (get_dp(slen, tlen) <= K)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
AtCoder Beginner Contest 386 Summary
2025/blog/45939/
Author
JoeyDDong
Published
2025-01-02 09:09
License
  1. A - Full House 2
  2. B - Calculator
  3. C - Operate 1
    1. 题目：
    2. 约束条件：
    3. 思路：
  4. D - Diagonal Separation
    1. 题目：
    2. 约束条件：
    3. 思路：
  5. E - Maximize XOR
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 前置知识 1：XOR 的性质
      2. 前置知识 2：组合数的性质
      3. 本题思路：
  6. F - Operate K
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 前置知识：“最短编辑距离”问题的标准做法：
      2. 本题的优化思路：带状区域计算 DP
      3. 注意点：
  1. A - Full House 2
  2. B - Calculator
  3. C - Operate 1
    1. 题目：
    2. 约束条件：
    3. 思路：
  4. D - Diagonal Separation
    1. 题目：
    2. 约束条件：
    3. 思路：
  5. E - Maximize XOR
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 前置知识 1：XOR 的性质
      2. 前置知识 2：组合数的性质
      3. 本题思路：
  6. F - Operate K
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 前置知识：“最短编辑距离”问题的标准做法：
      2. 本题的优化思路：带状区域计算 DP
      3. 注意点：