题解归档 - cf406E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf406E
• 本地来源：problems/cf406E/idea.md
• 题目链接：https://codeforces.com/contest/406/problem/E
• 原始标题：cf406E - Hamming Triples

思路

cf406E - Hamming Triples

Map each monotone binary string to a point on a circle of circumference 2n.

• 0^f 1^(n-f) -> coordinate f
• 1^f 0^(n-f) -> coordinate n+f

For two strings, their Hamming distance is exactly the circular distance of the two mapped points: same direction gives |f-g|, opposite direction gives n-|f-g|.

For three points on a circle of circumference 2n, let the three clockwise gaps be g1,g2,g3, and let M=max(g).

• if M <= n, the sum of pairwise circular distances is 2n;
• if M > n, the sum is 2 * (2n - M).

So the first target is all triples not covered by an arc of length < n; they reach the global upper bound 2n.

Sort all mapped points, duplicate with +2n, and for each left endpoint count following points with distance < n; choosing any two with it forms one uniquely counted short-arc triple.

If at least one triple is not short-arc, answer = all triples - short_arc_triples.

Otherwise every triple lies in an arc of length < n; then the best triples are exactly those with maximum minimal covering arc length. For each possible leftmost selected index i, keep the farthest far[i] with b[far[i]] - b[i] < n; this gives the maximum span starting at i. Count triples whose leftmost/rightmost selected indices have that global best span, with any middle selected index between them.

代码

来源：problems/cf406E/solution.cpp

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

using ll = long long;

ll C3(ll x) {
    return x * (x - 1) * (x - 2) / 6;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    int m;
    cin >> n >> m;
    vector<ll> a(m);
    for (int i = 0; i < m; i++) {
        int s;
        ll f;
        cin >> s >> f;
        a[i] = f + (s ? n : 0);
    }
    sort(a.begin(), a.end());
    vector<ll> b = a;
    for (ll x : a) b.push_back(x + 2 * n);

    ll bad = 0;
    int r = 0;
    vector<int> far(m);
    for (int l = 0; l < m; l++) {
        if (r < l) r = l;
        while (r + 1 < l + m && b[r + 1] - b[l] < n) r++;
        far[l] = r;
        ll cnt = r - l;
        bad += cnt * (cnt - 1) / 2;
    }

    ll total = C3(m);
    ll good = total - bad;
    if (good) {
        cout << good << '\n';
        return 0;
    }

    ll best = -1;
    for (int i = 0; i < m; i++) {
        if (far[i] - i >= 2) best = max(best, b[far[i]] - b[i]);
    }

    ll ans = 0;
    for (int i = 0; i < m; i++) {
        if (far[i] - i < 2) continue;
        ll target = b[i] + best;
        auto lo = lower_bound(b.begin() + i + 2, b.begin() + far[i] + 1, target);
        auto hi = upper_bound(b.begin() + i + 2, b.begin() + far[i] + 1, target);
        ll L = lo - b.begin();
        ll R = hi - b.begin() - 1;
        if (L > R) continue;
        ll cnt = R - L + 1;
        ans += (L + R) * cnt / 2 - cnt * (i + 1LL);
    }
    cout << ans << '\n';
    return 0;
}