「题解」写点 Codeforces 之 0x01

CF2021B

Info

给定有 $n$ 个正整数的数组 $a$ 和一个正整数 $x$，可以任意次地将 $a_i$ 加上 $x$。求不在数组 $a$ 中最小正整数的最大值。

Solution

记录数组中每一个数字出现的频率 $freq[x]$，显然有 $freq[x]=0$ 时取得需要的值。当 $freq[x]>1$ 时，我们可以把多出的 $freq[x]-1$ 个数字都加上 $x$（这里是一个贪心）。

Code

void solve() {
    int n, x;
    cin >> n >> x;
    map<int, int> freq;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        freq[x] ++;
    }
    int mex = -1;
    for (int i = 0; i <= n; i ++) {
        if (freq[i] == 0) {
            mex = i;
            break;
        }
        if (freq[i] > 1) {
            if (i + x > n)
                continue;
            freq[i + x] += freq[i] - 1;
            freq[i] = 1;
        }
    }
    cout << mex << '\n';
}

CF2000D

Info

给定一个有 $n$ 个正整数的数组 $a$，和长度为 $n$ 仅由 L 和 R 组成的字符串 $s_i$。可以对任意的一组对应的 L R 字符下标之间的 $a$ 数组元素求和，但求和之后这组 L R 就不可再次使用。求可能的求和之和的最大值。

考虑贪心，显然有先对内层的 L R 求和再对外层的求和可以取得求和之和最大。因此我们用双指针从外到内匹配 L 和 R 即可。考虑到本题有较多的求和操作，因此提前对数组 $a$ 做前缀和处理。

Code

void solve() {
    int n;
    cin >> n;
    vector<long long> vec(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> vec[i];
    for (int i = 1; i <= n; i ++)
        vec[i] += vec[i - 1];
    string s;
    cin >> s;
    int l = 0, r = n - 1;
    vector<pair<int, int>> range;
    while (l <= r) {
        if (s[l] == 'L' and s[r] == 'R') {
            range.push_back({l, r + 1});
            l ++;
            r --;
            continue;
        }
        if (s[l] != 'L')
            l ++;
        else if (s[r] != 'R')
            r --;
    }
    long long ans = 0;
    for (auto item : range) {
        ans += vec[item.second] - vec[item.first];
    }
    cout << ans << '\n';
}

CF1996C

Info

给定两个长度为 $n$ 字符串 $s_1$ 和 $s_2$，进行 $q$ 次查询，每次查询查询 $l$ 和 $r$ 之间两个字符串的子串需要多少次操作可以使得两个操作后的子串字典序排序后相同。

运用第一题相似的思路，对 $1$ 到 $n$ 之间求频率并作前缀和以持久化保存。显然有区间内二者每个字符频率之差绝对值的总和的一半为最少的修改次数。

Code

inline int c2i(char c) {
    return c - 'a';
}

void solve() {
    int n, q;
    cin >> n >> q;
    string s1, s2;
    cin >> s1;
    cin >> s2;
    s1 = " " + s1;
    s2 = " " + s2;
    vector<array<int, 26>> a1(n + 1);
    vector<array<int, 26>> a2(n + 1);
    for (int i = 1; i <= n; i ++) {
        a1[i][c2i(s1[i])] = 1;
        a2[i][c2i(s2[i])] = 1;
        for (int j = 0; j < 26; j ++) {
            a1[i][j] += a1[i - 1][j];
            a2[i][j] += a2[i - 1][j];
        }
    }
    while (q --) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int i = 0; i < 26; i ++) {
            ans += abs(a1[r][i] - a1[l - 1][i] - a2[r][i] + a2[l - 1][i]);
        }
        cout << ans / 2 << endl;
    }
}