Atcoder Beginner Contest 381 题解

发表于 更新于 分类于 阅读次数： 本文字数： 6.6k
迟来的11月22日的1122专场。

AtCoder Beginner Contest 380 题解

A

题意

定义“11/22“串为长度为奇数，中间为一个“/”，前面部分都是1，后面部分都是2。

现在给定一个字符串，判断是否满足是11/22串。

题解

由定义判断。

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n & 1) {
        for (int i = 0; i < n / 2; i++) {
            if (s[i] != '1') {
                cout << "No" << "\n";
                return;
            }
        }
        if (s[n / 2] != '/') {
            cout << "No" << "\n";
            return;
        }
        for (int i = n / 2 + 1; i < n; i++) {
            if (s[i] != '2') {
                cout << "No" << "\n";
                return;
            }
        }
        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;
}

B

题意

定义“1122串”为一个长度为偶数的字符串，第 \(2i\) 个位置和第 \(2i+ 1\) 个位置的字符相同，且每个字符最多只能出现两次。

现在给定一个字符串，判断是不是“1122”串。

题解

由定义判断。

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() {
    string s;
    cin >> s;
    if (s.size() & 1) {
        cout << "No" << "\n";
        return;
    }
    map<char, int> mp;
    int n = s.size();
    for (int i = 0; i < n; i += 2) {
        if (s[i] != s[i + 1]) {
            cout << "No" << "\n";
            return;
        }
        mp[s[i]] += 2;
        if (mp[s[i]] > 2) {
            cout << "No" << "\n";
            return;
        }
    }
    cout << "Yes" << "\n";
}

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

C

题意

给定一个字符串，求这个字符串的子串满足是“11/22”串的最大长度。（子串是连续的）

题解

考虑dp。设 \(f_i\) 表示以 \(i\) 结尾的子串的最长长度，那么根据 \(i\) 位置的字符分类考虑：如果是 1 的话，不能构成串，如果是 “/” 的话， \(f_i =1\) ，如果是 2 的话，还需要分情况：如果前一个位置也是 2 ，直接找对称位置是不是1，如果是的话有 \(f_i = f_{i-1} + 2\)，否则 \(f_i = 0\)；如果前一个位置是“/”的话，需要找再前一个位置是不是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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    vector<int> f(n);
    f[0] = s[0] == '/' ? 1 : 0;
    ans = f[0];
    for (int i = 1; i < n; i++) {
        if (s[i] == '1') {
            f[i] = 0;
        } else if (s[i] == '2') {
            if (i >= 2 && s[i - 2] == '1' && s[i - 1] == '/') {
                f[i] = 3;
            }
            if (s[i - 1] == '2') {
                if (i - 1 - f[i - 1] >= 0 && s[i - 1 - f[i - 1]] == '1') {
                    f[i] = f[i - 1] + 2;
                } else {
                    f[i] = 0;
                }
            }
        } else if (s[i] == '/') {
            f[i] = 1;
        }
        ans = max(ans, f[i]);
    }
    cout << ans << "\n";
}

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

D

题意

给定一个字符串，求这个字符串的子串满足是“1122”串的最大长度。（子串是连续的）

题解

考虑到满足“1122”串的子串每个字符最多出现两次，我们需要记录下每个位置之前出现当前字符的位置。

我们利用滑动窗口的思想，我们遍历右端点，考虑左端点的变化，维护能够满足条件的区间：即判断当前字符和后一个（或前一个）字符是否相等，不妨先考虑与后一个字符比较的情况，如果相等，这两个数必须要纳入答案，因此更新左端点为上一次出现该字符的位置之后，当然不能小于当前的左端点。如果不等，那么该区间不可能作为答案，将左端点放到右端点之后的位置。

由于区间长度必须是偶数，我们从 0 位置和 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> X(n);
    for (int i = 0; i < n; i++) {
        cin >> X[i];
        X[i]--;
    }
    int l = 0, ans = 0;
    vector<int> last(n + 1, -2);
    for (int i = 0; i + 1 < n; i += 2) {
        if (X[i] == X[i + 1]) {
            l = max(l, last[X[i]] + 2);
        } else {
            l = i + 2;
        }
        last[X[i]] = i;
        ans = max(ans, i + 2 - l);
    }
    l = 1;
    last.assign(n + 1, -2);
    for (int i = 1; i + 1 < n; i += 2) {
        if (X[i] == X[i + 1]) {
            l = max(l, last[X[i]] + 2);
        } else {
            l = i + 2;
        }
        last[X[i]] = i;
        ans = max(ans, i + 2 - l);
    }
    cout << ans << "\n";
}

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

E

题意

给定一个字符串和 \(Q\) 次询问，每次询问给定 \(L,R\) ，求区间 \([L,R]\) 中子序列最大“11/22”串长度。（子序列可以不连续）

题解

对于子序列的特殊性，我们可以对于每一个“/”字符求出左边的“1”个数和右边的“2”个数。但是考虑区间查询，每一个“/”的左边的“1”个数和右边的“2”个数可以通过差分得到，但是我们主要的问题是怎么找到区间内的“/”。由于我们最后的答案一定是取两种个数的最小值后乘 2 加 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
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    int cnt1 = 0, cnt2 = 0;
    vector<int> pre1(N), pre2(N);
    vector<int> a;
    for (int i = 0; i < N; i++) {
        if (s[i] == '1') {
            cnt1++;
        } else if (s[i] == '2') {
            cnt2++;
        } else {
            a.push_back(i);
        }
        pre1[i] = cnt1, pre2[i] = cnt2;
    }
    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int ans = 0;
        int lo = 0, hi = a.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] > r) {
                hi = mid;
            } else if (a[mid] < l) {
                lo = mid + 1;
            } else {
                int c1, c2;
                if (l == 0) {
                    c1 = pre1[a[mid]];
                } else {
                    c1 = pre1[a[mid]] - pre1[l - 1];
                }
                c2 = pre2[r] - pre2[a[mid]];
                ans = max(ans, min(c1, c2) * 2 + 1);
                if (c1 < c2) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
        }
        cout << ans << "\n";
    }
}

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

F

题意

给定一个数组 \(A_i\) ，求这个数组的子序列中“1122”串长度的最大值。

\(A_i\le 20\)

题解

考虑到 \(A_i\) 数据很小，考虑状态压缩，设 \(f_{i,j}\) 表示前缀长度为 \(i\) ，状态为 \(j\) 是否存在答案，那么时间复杂度为 \(O(n2^{20})\)，还是不足以通过本题。考虑优化，其实我们只需要知道最小的前缀长度即可，因为这样可以贪心地尽可能扩大答案。

我们设 \(f_i\) 表示状态为 \(i\) ，取前 \(f_i\) 个数。那么状态转移应该是由小到大，转移时需要在当前状态添加一个不属于状态中已有的数，为了转移，我们还需要 \(i\) 位置下一个出现 \(j\) 的位置，记为 \(\text{nxt}_{i,j}\) ，那么应该有 \(f_{i+j} = \min\{\text{nxt}_{\text{nxt}_{f_i,j},j}\}\)​。

时间复杂度：\(O(20n + 20\times2^{20})\)

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;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    vector<vector<int>> nxt(N + 2, vector<int>(20));
    for (int i = 0; i < 20; i++) {
        nxt[N][i] = nxt[N + 1][i] = N + 1;
    }
    for (int i = N; i >= 1; i--) {
        for (int j = 0; j < 20; j++) {
            nxt[i - 1][j] = nxt[i][j];
            nxt[i - 1][A[i - 1]] = i;
        }
    }
    int ans = 0;
    vector<int> f((1ll << 20));
    f[0] = 0;
    for (int i = 1; i < (1ll << 20); i++) {
        int cnt = 0;
        f[i] = N + 1;
        for (int j = 0; j < 20; j++) {
            if (i & (1 << j)) {
                cnt++;
                f[i] = min(f[i], nxt[nxt[f[i ^ (1 << j)]][j]][j]);
            }
        }
        if (f[i] <= N) {
            ans = max(ans, cnt);
        }
    }
    cout << ans * 2 << "\n";
}

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