AtCoder Beginner Contest 381

• A. 按题意判断即可
• B. 按题意判断即可
• C. 枚举/的位置，然后分别向左右找到最长的1串和2串，然后取最小值即可
• D. 讨论起始位置的奇偶性，然后用双指针，每两个字符每两个字符，维护出现的次数为2，两种情况取最大值即可
• E. 答案为所有/的左右12个数的最小值的最大值，注意到个数随着/的增大是单调的，而最大值出现在交点，二分找该交点即可
• F. \(dp[i]\)表示已经选择的字符的集合状态是\(i\)时的最小的选择字符的位置，转移枚举下一个字符，然后找到下一个字符的位置，然后更新\(dp\)即可

n = input()
s = input()
s = s.split('/')
if len(s) == 2 and len(s[0]) == len(s[1]) and all(i == '1' for i in s[0]) and all(i == '2' for i in s[1]):
    print('Yes')
else:
    print('No')

s = input()
c = set(s)
if s[::2] == s[1::2] and all(sum(1 for i in s if i == j) == 2 for j in c):
    print('Yes')
else:
    print('No')

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    auto find1 = [&](int x) {
        for (int i = x; i >= 0; --i) {
            if (s[i] != '1')
                return x - i;
        }
        return x + 1;
    };
    auto find2 = [&](int x) {
        for (int i = x; i < n; ++i) {
            if (s[i] != '2')
                return i - x;
        }
        return n - x;
    };
    for (int i = 0; i < n; i++) {
        if (s[i] == '/') {
            ans = max(ans, min(find1(i - 1), find2(i + 1)));
        }
    }
    ans = ans * 2 + 1;
    cout << ans << '\n';

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a) {
        cin >> i;
        --i;
    }
    auto solve = [&](int st) {
        int ret = 0;
        int la = st;
        vector<int> cnt(n);
        for (int i = st; i < n; i += 2) {
            if (i + 1 >= n || a[i] != a[i + 1] || cnt[a[i]] == 1) {
                ret = max(ret, i - la);
                while (la < i && (a[i] != a[i + 1] || cnt[a[i]] == 1)) {
                    cnt[a[la]]--;
                    la += 2;
                }
            }
            if (a[i] == a[i + 1])
                cnt[a[i]]++;
            else
                la += 2;
        };
        ret = max(ret, n - la - ((n - st) & 1));
        return ret;
    };
    int ans = max(solve(0), solve(1));
    cout << ans << '\n';

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    string s;
    cin >> n >> q >> s;
    array<vector<int>, 2> cnt{vector<int>(n), vector<int>(n)};
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        if (s[i] == '/')
            pos.push_back(i);
        else
            cnt[s[i] - '1'][i] = 1;
    }
    partial_sum(cnt[0].begin(), cnt[0].end(), cnt[0].begin());
    partial_sum(cnt[1].begin(), cnt[1].end(), cnt[1].begin());
    auto get_sum = [&](int l, int r, int c) {
        return cnt[c][r] - (l - 1 < 0 ? 0 : cnt[c][l - 1]);
    };
    auto solve = [&](int L, int R) {
        auto calc1 = [&](int x) { return get_sum(L, x, 0); };
        auto calc2 = [&](int x) { return get_sum(x, R, 1); };
        auto check = [&](int x) { return calc1(x) <= calc2(x); };

        int l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
        int r = upper_bound(pos.begin(), pos.end(), R) - pos.begin();
        if (l == r)
            return 0;
        int ret = 0;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (check(pos[m]))
                l = m;
            else
                r = m;
        }
        for (int i = l; i <= r; i++) {
            if (L <= pos[i] && pos[i] <= R)
                ret = max(ret, min(calc1(pos[i]), calc2(pos[i])));
        }
        return ret * 2 + 1;
    };
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        int ans = solve(l, r);
        cout << ans << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    constexpr int num = 20;
    array<vector<int>, num> pos;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        --a;
        pos[a].push_back(i);
    }
    constexpr int up = (1 << num);
    vector<int> dp(up, n);
    dp[0] = 0;
    int ans = 0;
    for (int i = 0; i < up; ++i) {
        for (int j = 0; j < num; ++j) {
            if ((i >> j) & 1) {
                int la = i ^ (1 << j);
                auto it = lower_bound(pos[j].begin(), pos[j].end(), dp[la]);
                if (it != pos[j].end() && next(it) != pos[j].end()) {
                    dp[i] = min(dp[i], *next(it));
                    ans = max(ans, __builtin_popcount(i));
                }
            }
        }
    }
    cout << ans * 2 << '\n';

    return 0;
}