Educational Codeforces Round 171 (Rated for Div. 2)

比赛链接

Problems	AC
A. Perpendicular Segments	○
B. Black Cells	○
C. Action Figures	○
D. Sums of Segments	○
E. Best Subsequence	○
F. Bermart Ice Cream

C

最有意思的一个题。由于所有的东西都要买，转化为最多能用多少优惠。

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

    string s;
    cin >> s;

    s = '#' + s;
    int ans = 0;

    std::queue<int> q;
    for (int i = n; i >= 1; i--) {
        if (s[i] == '0') {
            ans += i;
            if (!q.empty()) {
                q.pop();
            }
        } else {
            q.ep(i);
        }
    }

    int m = q.size() / 2;
    while (m--) q.pop();

    while (!q.empty()) {
        ans += q.front();
        q.pop();
    }
 
    cout << ans << '\n';
}

D

分块前缀和套前缀和，算算算算就过了。

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

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        // siz[i] = n - i + 1;
    }

    vector<int> suma(n + 1);
    for (int i = 1; i <= n; i++) {
        suma[i] = suma[i - 1] + a[i];
    }

    vector<int> sum2a(n + 1);
    for (int i = 1; i <= n; i++) {
        sum2a[i] = sum2a[i - 1] + suma[i];
    }

    vector<int> block_sum(n + 1);
    block_sum[1] = sum2a[n];
    for (int i = 2; i <= n; i++) {
        block_sum[i] = block_sum[i - 1] - a[i - 1];
        block_sum[i] -= (n - i + 1) * (a[i - 1]);
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << block_sum[i] << '\n';
    // }

    for (int i = 1; i <= n; i++) {
        block_sum[i] += block_sum[i - 1];
    }

    auto get = [&](int x) {
        int res = 0;

        int p = 0;
        for (int l = 1, r = n; l <= r; ) {
            int mid = l + r >> 1;
            if ((n + n - mid + 1) * mid / 2 < x) {
                p = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        res += block_sum[p];

        x -= (n + n - p + 1) * p / 2;
        res += sum2a[x + p] - sum2a[p] - suma[p] * x;
        return res;
    };

    for (int q = read(); q--; ) {
        int l = read(), r = read();
        cout << get(r) - get(l - 1) << '\n';
        // cout << get(r) << '\n';
    }
}

E

最大权闭合子图。

从 s 向 1…n 连 1

1…n 向 1…60 中对应的 bit 位连 inf。

1…60 向 t 连 1。

经典结论之：最大权闭合子图的权值等于所有正权点（与 s 直接相连的点集）权值之和减去最小割

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

    MaxFlow<int> g(n + 1 + 60 + 2);

    int node = n + 60;
    int s = ++node;
    int t = ++node;

    for (int i = 1; i <= 60; i++) {
        g.addEdge(n + i, t, 1);
    }

    for (int i = 1; i <= n; i++) {
        int x = read();
        g.addEdge(s, i, 1);
        for (int j = 0; j < 60; j++) {
            if (x >> j & 1) {
                g.addEdge(i, n + j + 1, inf);
            }
        }
    }

    cout << n - g.flow(s, t) << '\n';
}