Atcoder Beginner Contest 393 + 394 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.2k
加训加训。

AtCoder Beginner Contest 393 题解

D

题意

给定一个 01 串，可以交换相邻两个字符的位置，求让字符串中所有 1 都连在一起的最小交换次数。

题解

等价地，我们可以考虑把字符 0 放到整个字符串的左边或右边，因此贪心即可，只需要看左边的 1 多还是右边的 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
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N;
    cin >> N;
    N++;
    string s;
    cin >> s;
    s = " " + s;
    int c1 = 0;
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        c1 += (s[i] == '1');
    }
    int now = 0;
    for (int i = 1; i <= N; i++) {
        if (s[i] == '0') {
            ans += min(now, c1 - now);
        } else {
            now++;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定一个序列 \(A\)，求对于每一个位置 \(i\)，求在序列中选择 \(K\) 个数（必须选择 \(A_i\)）组成的最大 GCD 是多少。

\(A_i\le 10^6\)

题解

GCD 没有什么特别好的性质，一般遇到了只能枚举，由于值域不算很大，我们从大到小枚举值域内每一个数 \(i\)作为 \(K\) 个数的 GCD 的情形，再通过枚举 \(i\) 的倍数，我们通过判断倍数的出现次数是否大于或等于 \(K\)，如果成立，\(i\)​ 就可以作为它们的 GCD。

这样枚举的时间复杂度应该是调和级数\(O(n\log n)\)，可以通过，但是用 vector 被卡了一下，去掉#define int long long才过。

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
#include <bits/stdc++.h>
using namespace std;
// #define int long long

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N + 1), ans(N + 1);
    int mx = 1;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        mx = max(mx, A[i]);
    }
    vector<vector<int>> v(mx + 1);
    for (int i = 1; i <= N; i++) {
        v[A[i]].push_back(i);
    }
    for (int i = mx; i >= 1; i--) {
        vector<int> tmp;
        for (int j = i; j <= mx; j += i) {
            if (v[j].size()) {
                for (auto y : v[j]) {
                    tmp.push_back(y);
                }
            }
        }
        if (tmp.size() >= K) {
            for (auto x : tmp) {
                ans[x] = max(ans[x], i);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一个序列 \(A\) 和 \(Q\) 次询问，每次询问给出一个 \(R\) 和 \(X\)，求 \(A_1\) 到 \(A_R\) 的一个最长严格单调子序列，它的最大值不能超过 \(X\)，给出这个子序列的长度。

题解

显然需要离线处理，我们按照 \(R\) 排序，问题就是如何找到求最长严格单调子序列（LIS）的长度了。

由于我们只需要求长度和最大值，LIS有这样的处理方式：

  1. 从已经维护的 LIS 数组中二分查找第一个大于或等于当前判断的数
  2. 如果不存在，它就是最大的，直接加到 LIS 末尾
  3. 如果存在，用当前值替换掉找到的位置对应的数

这样处理，LIS数组末尾就是最大的数，而里面的数不一定有序，LIS 数组的含义为：当前可能的LIS末尾元素的最小值（用1-index的话，LIS[i]就是长度为1的单调子序列，末尾最小是 \(i\)），因此寻找不大于 \(X\) 的数时也可以进行二分查找。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> ans(q + 1);
    vector<array<int, 3>> e(q + 1);
    for (int i = 1; i <= q; i++) {
        int r, x;
        cin >> r >> x;
        e[i][0] = r;
        e[i][1] = x;
        e[i][2] = i;
    }
    sort(e.begin() + 1, e.end());
    int hi = 1;
    vector<int> lis;
    for (int i = 1; i <= q; i++) {
        int r = e[i][0], x = e[i][1], id = e[i][2];
        for (; hi <= r; hi++) {
            auto it = lower_bound(lis.begin(), lis.end(), a[hi]);
            if (it == lis.end()) {
                lis.push_back(a[hi]);
            } else {
                *it = a[hi];
            }
        }
        int c = upper_bound(lis.begin(), lis.end(), x) - lis.begin();
        ans[id] = c;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394) 题解

D

题意

给定一个括号序列，当且仅当遇到连续的 “()”，“<>”，“{}”时才能消除，判断能否全部消除。

题解

很简单的括号匹配，用栈即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    s = " " + s;
    int n = s.size();
    stack<char> stk;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '<') {
            stk.push(s[i]);
        }
        if (s[i] == ')') {
            if (stk.empty() || stk.top() != '(') {
                cout << "No\n";
                return;
            }
            stk.pop();
        }
        if (s[i] == ']') {
            if (stk.empty() || stk.top() != '[') {
                cout << "No\n";
                return;
            }
            stk.pop();
        }
        if (s[i] == '>') {
            if (stk.empty() || stk.top() != '<') {
                cout << "No\n";
                return;
            }
            stk.pop();
        }
    }
    if (stk.empty()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定一张有向图，每条边上都有着一个字母，求所有的两点之间是否存在一条路径构成一个回文串，如果存在，输出最短长度，否则输出 -1。

题解

我们从回边和长度为 1 的边拓展，通过 BFS，例如从 \(i\) 到 \(j\) 的路径是一条回文串，那么考虑 \(x\rightarrow i\) 和 \(j\rightarrow y\)，如果字母相同就可以拓展。使用 BFS 即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N;
    cin >> N;
    vector<vector<char>> e(N + 1, vector<char>(N + 1));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> e[i][j];
        }
    }
    vector<vector<int>> ans(N + 1, vector<int>(N + 1, 1e18));
    queue<pair<int, int>> q;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                ans[i][j] = 0;
                q.push({i, j});
            }
            if (i != j && e[i][j] != '-') {
                ans[i][j] = 1;
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 1; i <= N; i++) {
            if (e[i][x] != '-') {
                for (int j = 1; j <= N; j++) {
                    if (e[y][j] != '-') {
                        if (e[i][x] == e[y][j]) {
                            if (ans[i][j] > ans[x][y] + 2) {
                                ans[i][j] = ans[x][y] + 2;
                                q.push({i, j});
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << (ans[i][j] == 1e18 ? -1 : ans[i][j]) << " \n"[j == N];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一颗树，求它的一颗子树是否满足：每个节点的度数都是 1 或 4，且至少有一个度数为 4 的节点。给出子树的最大大小或判断不存在。

题解

首先可以通过统计度数来判断是否存在。我们可以认为除了根节点，其他所有节点都要满足儿子数量为 3 或 0 ，考虑树上 dp，设 \(f_{i,j}\) 代表根为 \(x\)，儿子节点为 \(j\) 的最大子树大小。初始时 \(f_{i,0} = 1\)，转移方程有\(f_{x,j} = \max(f_{x,j-1} + \max(f_{y,0},f_{y,3}))\)。而对于整颗子树的答案，既然有至少有一个节点度数为 4 的限制，如果根节点只保留一个儿子的话，需要 \(f_{x,1} \ge 3\)，因此 \(\text{ans} = \max(f_{x,4},f_{x,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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> e(N + 1);
    vector<int> d(N + 1);
    for (int i = 1; i <= N - 1; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        d[x]++;
        d[y]++;
    }
    bool ok = false;
    for (int i = 1; i <= N; i++) {
        if (d[i] >= 4) {
            ok = true;
            break;
        }
    }
    if (!ok) {
        cout << -1 << "\n";
        return;
    }
    int ans = -1;
    vector<vector<int>> f(N + 1, vector<int>(5, -1e9));
    auto dfs = [&](auto self, int x, int fa) -> void {
        f[x][0] = 1;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            self(self, y, x);
            for (int j = 4; j >= 1; j--) {
                f[x][j] = max(f[x][j], f[x][j - 1] + max(f[y][0], f[y][3]));
            }
        }
        if (f[x][1] >= 3) {
            ans = max(ans, f[x][1]);
        }
        ans = max(ans, f[x][4]);
    };
    dfs(dfs, 1, 0);
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}