题解-Codeforces Round 1054 (Div. 3)

5 -> 4 , 哭死了，再也不用unordered_map了![[01E9AA9D.png]]

A

整数不用管，有0就加一，统计所有的负数，如果负数的个数为偶数，不用管，否则加上最小的负数的绝对值再加一。

void solve() {
    int n ;cin >> n;
    vi v;
    int a = 0;
    int ans = 0;
    for(int i = 0; i < n; ++ i) {
        cin >> a;
        if(a < 0) {
            v.push_back(a);
        }
        if(a == 0) {
            ans ++;
        }
    }
    sort(all(v));
    if(sz(v) % 2 == 0) {
        cout << ans << "\n";
    } else cout << ans - v[0]  + 1 << "\n";
}

B

排序，每两个找相邻的最大的间隔。

void solve() {
    int n; cin >> n;
    vi v(n);
    for(int i = 0; i < n; ++ i) {
        cin >> v[i];
    }
    int mx = 0;
    sort(all(v));
    for(int i = 0; i < n; i += 2) {
        mx = max(v[i + 1] - v[i], mx);
        
    }
    cout << mx << "\n";
}

C

k之前没出现过的元素的数量和k的数量的最大值。

void solve() {
    int n, k; cin >> n >> k;
    vi v(n);
    map<int, int> mp;
    int cnt = 0;
    for(int i = 0; i < n; ++ i) {
        cin >> v[i];
        mp[v[i]] ++;
    }
    int ans = 0;
    for(int i = 0; i < k; ++  i) {
        if(mp[i] == 0) {
            ans ++;
        }
    }
    ans = max(ans, mp[k]);
    cout << ans << "\n";
}

D

任意两个元素之间换位置，费用为他们之间的距离。

以某个元素为块，最优解就是向中间元素靠近。

尝试以$a$或者以$b$为块所需要的费用，取最小值。

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int cnta = count(all(s), 'a');
    int idx = (cnta + 1) / 2;
    int mid = 0;
    int cnt = 0;
    for(int i = 0; i < n; ++ i) {
        if(s[i] == 'a') {
            cnt ++;
        }
        if(cnt == idx) {
            mid = i;
            break;
        }
    }
    int l = mid, r = mid;
    int ans1 = 0;
    for(int i = mid; i >= 0; -- i) {
        if(s[i] == 'a') {
            ans1 += abs(l - i);
            l --;
        }
    }
    for(int i = mid; i < n; ++ i) {
        if(s[i] == 'a') {
            ans1 += abs(i - r);
            r ++;
        }
    }
    int cntb = count(all(s), 'b');
    idx = (cntb + 1) / 2;
    mid = 0;
    cnt = 0;
    for(int i = 0; i < n; ++ i) {
        if(s[i] == 'b') {
            cnt ++;
        }
        if(cnt == idx) {
            mid = i;
            break;
        }
    }
    int ans2 = 0;
    l = mid, r = mid;
    for(int i = mid; i >= 0; -- i) {
        if(s[i] == 'b') {
            ans2 += abs(l - i);
            l --;
        }
    }
    for(int i = mid; i < n; ++ i) {
        if(s[i] == 'b') {
            ans2 += abs(i - r);
            r ++;
        }
    }
    cout << min(ans1, ans2) << "\n";
}

E

真的要哭死了，赛时的unordered_map过了，赛后超时了，真的以后把unordered_map给禁了，map随便用。

双指针，先找出所有元素数量小于等于 $k$ 的合法区间的数量，再找出元素数量小于 $k$ 的合法区间数量，减去之后，就是元素数量等于 $k$ 的合法区间数量。

void solve() {
    int n, k, L, R; cin >> n >> k >> L >> R;
    vi v(n);
    for(int i = 0; i < n; ++ i) cin >> v[i];

    map<int,int> cnt;
    int d = 0;
    int l = 0;
    int ans1 = 0;

    for (int r = 0; r < n; r++) {
        cnt[v[r]]++;
        if (cnt[v[r]] == 1) d++;

        while (d > k) {
            cnt[v[l]]--;
            if (cnt[v[l]] == 0) d--;
            l++;
        }

        int minl = max(l, r - R + 1);
        int maxl = r - L + 1;
        if (maxl >= minl) {
            ans1 += (ll)(maxl - minl + 1);
        }
    }
    map<int,int> cnt1;
    d = 0;
    l = 0;
    int ans2 = 0;
    k --;
    for (int r = 0; r < n; r++) {
        cnt1[v[r]]++;
        if (cnt1[v[r]] == 1) d++;

        while (d > k) {
            cnt1[v[l]]--;
            if (cnt1[v[l]] == 0) d--;
            l++;
        }

        int minl = max(l, r - R + 1);
        int maxl = r - L + 1;
        if (maxl >= minl) {
            ans2 += (ll)(maxl - minl + 1);
        }
    }
    cout << ans1 - ans2 << "\n";
}

幸好还是加分了（低分的蒟蒻）