Codeforces Round 1011 (Div.2) 题解

A

题意

给定一个字符串，可以选择两个位置的字符交换 \(k\) 次，求是否能让这个字符串的字典序小于它的倒序。

题解

首先 \(k = 0\) 时就直接比较字典序即可，否则的话如果这个字符串由相同字符构成就不能成立，除此之外一定成立，因为在比较过程中一旦出现字典序相等或大于倒序的，就换一个小于的字符来。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    if (k == 0) {
        if (s < t) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
        return;
    }
    if (count(s.begin(), s.end(), s[0]) == n) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个长度大于 4 的数组 \(a\)，你可以进行下面的操作：选择两个位置 \(l<r\)，将 $a_l $ 到 \(a_r\) 换成这个区间内的 \(\text{mex}\)。要求输出一个方案，使得数组里只剩下一个 0。

题解

如果数组没有 0 元素，我们直接选择两端就行了，如果有零，我们就可以把零消掉，这里分情况讨论：如果零在区间首位都出现了，那么必须分三次操作：选择前缀，选择后缀，选择全部——这样才能消去零。否则的话我们直接选择包含零的极大区间然后再选择全部数即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            if (l == 0) {
                l = i;
                r = i;
            } else {
                r = i;
            }
        }
    }
    if (l == 1 && r == n) {
        cout << 3 << "\n";
        cout << 1 << " 2\n";
        cout << 2 << " " << n - 1 << "\n";
        cout << 1 << " " << 2 << "\n";
        return;
    }
    if (l != 0 && l == r) {
        if (l == 1) {
            r++;
        } else {
            l--;
        }
    }
    if (l == 0) {
        cout << 1 << "\n";
        cout << 1 << " " << n << "\n";
    } else {
        cout << 2 << "\n";
        cout << l << " " << r << "\n";
        cout << 1 << " " << n + l - r << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定两个数 \(x,y \le 10^9\)，找到一个数 \(0\le k\le 10^{18}\) 满足 \((x+k) + (y + k) = (x+k)\oplus (y+k)\)。

题解

显然的一个性质是，最终形成的 \((x+k)\) 和 \((y+k)\) 的二进制每一位不能同时出现 1。那么，不妨就让其中最大的数为 1000...000，另一个数比它小，就满足题意了。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int x, y;
    cin >> x >> y;
    if (x == y) {
        cout << -1 << "\n";
    } else {
        cout << (1 << 30) - max(x, y) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

\(n\) 个零食按时间依次供应，它们具有值 \(a_i\) 。在第 \(i\) 分钟你可以拿走 \(a_i\)，每个零食需要 \(k\) 分钟吃完，如果某一分钟你选择了拿零食，这一分钟就不能吃，并且必须要在第 \(n\) 分钟结束时，你拿的零食都吃完了，求能获得的最大值。

题解

如果只能拿一次，最后一次拿零食的最晚时间是 \(n - k\)，在此时，之前出现的所有零食实际上我们都可以拿，因此，每当第 \((n+1-x(k+1))\)​ 分钟时，我们可以拿走在此之前出现过的最大值，相当于把这期间出现的所有零食放到此刻选择，因为这是最大的拿零食的次数，不会有更多次了，可以选择贪心的拿最大值。因此，我们开一个优先队列，每当到了这样的时刻选择最大值即可。

正确性是显然的，从后往前看，不能多拿后出现的数，否则没有时间吃完。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() 
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    priority_queue<int> pq;
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        pq.push(a[i]);
        if ((n - i + 1) % (k + 1) == 0) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}