CodeTON Round 6 (Div. 1 + Div. 2) 题解 | JorbanS

A - MEXanized Array

int solve() {
    int n, k, x; cin >> n >> k >> x;
    if (n < k || k > x + 1) return -1;
    int res = k * (k - 1) / 2;
    if (x > k) res += (n - k) * x;
    else res += (n - k) * (k - 1);
    return res;
}
1
2
3
4
5
6
7
8

B - Friendly Arrays

void solve() {
    int n, m; cin >> n >> m;
    bool flag = n & 1;
    int A_XOR = 0, B_OR = 0;
    while (n --) {
        int x; cin >> x;
        A_XOR ^= x;
    }
    while (m --) {
        int x; cin >> x;
        B_OR |= x;
    }
    int res;
    if (flag) res = A_XOR | B_OR;
    else res = (A_XOR | B_OR) ^ B_OR;
    cout << min(A_XOR, res) << ' ' << max(A_XOR, res) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C - Colorful Table

void solve() {
    cin >> n >> m;
    vector<vector<int>> e(m + 1);
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        e[x].push_back(i);
    }
    int l = n, r = 1;
    vector<int> ans(m + 1);
    for (int i = m; i; i --) {
        if (e[i].size() == 0) continue;
        for (auto j : e[i]) {
            l = min(l, j);
            r = max(r, j);
        }
        ans[i] = r - l + 1 << 1;
    }
    for (int i = 1; i <= m; i ++) cout << ans[i] << ' ';
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

D - Prefix Purchase

题解 先取最小值，用最小值尽可能进行操作，会剩下一些硬币，用剩下的硬币，取最小值后方的次小值，花费代价进行替换，每次最多的次数即为替换前面的次数。因此维护一个后缀最小值即可，每次如果和前面的最小值相等，则无需进行操作，否则进行次小值替换上一个被替换的数

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> c[i];
    for (int i = n - 1; i >= 1; i --) c[i] = min(c[i], c[i + 1]);
    int k; cin >> k;
    int res = k % c[1];
    ans[1] = k / c[1];
    for (int i = 2; i <= n; i ++) {
        int dx = c[i] - c[i - 1];
        if (!dx) ans[i] = ans[i - 1];
        else {
            ans[i] = min(ans[i - 1], res / dx);
            res -= ans[i] * dx;
        }
    }
    for (int i = 1; i <= n; i ++) cout << ans[i] << ' ';
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18