Educational Codeforces Round 180 (Rated for Div. 2)

A. Candies for Nephews

模 3 剩多少能凑够 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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

typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7, inf = 1e9;

void solve() {
    int n;
    cin >> n;
    cout << (3 - n % 3) % 3 << "\n";
}

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

B. Deck of Cards

2 操作可最后考虑，先处理所有的 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


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

typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7, inf = 1e9;

void solve() {
    int n, k;
    cin >> n >> k;
    int l = 1, r = n, cnt = 0;
    for (int i = 1; i <= k; i++) {
        char x;
        cin >> x;
        if (x == '0') {
            l++;
        } else if (x == '1') {
            r--;
        } else cnt++;
    }
    string ans;
    ans.resize(n + 1, '+');
    for (int i = 1; i < l; i++) {
        ans[i] = '-';
    }
    for (int i = n; i > r; i--) {
        ans[i] = '-';
    }
    if (cnt >= r - l + 1) {
        for (int i = l; i <= r; i++) {
            ans[i] = '-';
        }
        cout << ans.substr(1, n) << '\n';
        return;
    }
    if (l >= r) {
        cout << ans.substr(1, n) << '\n';
        return;
    }
    if (r - l + 1 <= cnt * 2) {
        for (int i = l; i <= r; i++) {
            ans[i] = '?';
        }
    } else {
        for (int i = l; i <= l + cnt - 1; i++) {
            ans[i] = '?';
        }
        for (int i = r; i >= r - cnt + 1; i--) {
            ans[i] = '?';
        }
    }
    cout << ans.substr(1, n) << "\n";
}

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

C. Monocarp’s String

原串 a b 数量差值反过来，即为删除片段需要的差值，记 a 为 1，b 为 -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


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

void solve() {
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    vector<int> pre(n + 1, 0);
    map<int, vector<int>> pos;

    pos[0].push_back(0); 

    int cnta = 0, cntb = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'a') {
            cnta++;
            pre[i] = pre[i - 1] + 1;
        } else {
            cntb++;
            pre[i] = pre[i - 1] - 1;
        }
        pos[pre[i]].push_back(i);
    }

    if (cnta == cntb) {
        cout << 0 << "\n";
        return;
    }

    int ned = cnta - cntb;
    int ans = n;

    for (int i = 0; i <= n; i++) {  
        int t = pre[i] + ned;
        if (!pos.count(t)) continue;
        auto it = lower_bound(pos[t].begin(), pos[t].end(), i + 1);
        if (it != pos[t].end())
            ans = min(ans, *it - i);
    }

    if (ans == n) ans = -1;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

D. Inversion Value of a Permutation

当前序列后加入一个比前面都小的元素，假设当前序列长度为 len, 那么就会为总贡献增加 len。

按这个思路，记 $f_{i,j}$ 为第 i 位元素，总贡献为 j 是否可达。