Educational Codeforces Round 169 (Rated for Div. 2)

比赛链接

Problems	AC
A. Closest Point	○
B. Game with Doors	○
C. Splitting Items	○
D. Colored Portals	○
E. Not a Nim Problem	⊕
F. Make a Palindrome
G. Substring Compression

A

只能是 2 个点的情况，且得有空隙插

B

分类讨论区间包含情况即可

C

策略是唯一的

void solve() {
    int n = read(), k = read();

    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = read();
    std::sort(a.rbegin(), a.rend());

    int ans = 0;
    for (int i = 1; i < n; i += 2) {
        int t = min(k, a[i - 1] - a[i]);
        k -= t, a[i] += t;
    }

    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) ans += a[i];
        else ans -= a[i];
    }

    cout << ans << '\n';
}

D

要么是可以直接跳，要么是向左或者向右各找一个最近的跳看看哪个小。如果不是最近的话肯定劣于最近的。预处理一下即可。

const std::string color = "BGRY";

int id(int x, int y) {
    if (x > y) swap(x, y);
    return y * (y - 1) / 2 + x;
}

void solve() {
    int n = read(), q = read();
    
    vector<std::array<int, 2>> c(n + 2);
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        
        for (int j = 0; j < 2; j++) {
            c[i][j] = color.find(s[j]);
        }
    }

    vector<std::array<int, 6>> pre(n + 1), nxt(n + 1);

    for (int i = 1; i <= n; i++) {
        if (i == 1) pre[i].fill(0);
        else pre[i] = pre[i - 1];
        pre[i][id(c[i][0], c[i][1])] = i;
    }
    for (int i = n; i >= 1; i--) {
        if (i == n) nxt[i].fill(n + 1);
        else nxt[i] = nxt[i + 1];
        nxt[i][id(c[i][0], c[i][1])] = i;
    }

    for (int i = 0; i < q; i++) {
        int x = read(), y = read();
        int ans = 1e9;
        if (x > y) swap(x, y);
        for (auto a : c[x]) {
            for (auto b : c[y]) {
                if (a == b) ans = y - x;
                else {
                    int w = id(a, b);
                    for (auto z : {nxt[x][w], pre[y][w]}) {
                        if (1 <= z and z <= n) {
                            ans = min(ans, abs(x - z) + abs(y - z));
                        }
                    }
                }
            }
        }

        cout << (ans == 1e9 ? -1 : ans) << "\n";
    }
}

E

Code