Codeforces Round 1011 (Div. 2) A-E 题解

A - Serval and String Theory

Code

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

int main() {
    // freopen ("A.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        string S; cin >> S;
        map<char, int> mp;
        for (int i = 0; i < N; i++)
            mp[S[i]]++;
        if (mp.size() == 1) {
            cout << "NO\n";
            continue;
        }
        if (K == 0) {
            string S_ = S;
            reverse(S_.begin(), S_.end());
            if (S < S_) cout << "YES\n";
            else cout << "NO\n";
        }
        else {
            cout << "YES\n";
        }
    }

    return 0;
}

B - Serval and Final

Question

给定一个数组 $a$ ，你需要进行操作，直到数组长度为 $1$

选择两个数 $l, r (1 \leq l < r \leq | a |)$ 用单个数 $m e x (a_{l}, a_{l + 1}, \dots, a_{r})$ 替换 $l, r$ 区间里面的数

要求最后一个元素为 $0$ ，要求给出一种方案，不要求最小化操作次数

Solution

我的解法比较麻烦

如果全 $0$ 的话，分成两半处理即可
如果全非 $0$ ，那么 $l = 1, r = n$ 即可

对于有 $0$ 有非 $0$ 的，考虑转化成全非 $0$

我们发现 $n$ 的大小为 $5000$ ，可以做到 $n^{2}$

每次从头找，如果发现一个 $0$ 的位置为 $i$ ，那么让 $i$ 和 $i$ 边上的元素做一次 $m e x$ 操作即可消除 $i$ 位置的 $0$ ，然后去模拟题中的操作直到串中没有 $0$ 或者串的长度为 $1$

每次都从头处理，每次模拟 $O (n)$ ，总时间复杂度 $O (n)$

Code

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

void solve() {
    int N; cin >> N;
    vector<int> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    map<int, int> mp;

    auto Mex = [&] (vector<int> &A) {
        mp.clear();
        for (int i = 0; i < A.size(); i++)
            mp[A[i]] += 1;
        for (int i = 0; i > -1 ; i++)
            if (mp[i] == 0) return i;
        return 0;
    };


    vector<pair<int, int>> ans;
    
    auto print = [&] () {
        assert(N == 1 and A[1] == 0);
        cout << ans.size() << '\n';
        for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
    };

    auto check = [&] (int l, int r) {
        ans.push_back({l, r});
        vector<int> b;
        for (int i = l; i <= r; i++)
            b.push_back(A[i]);
        int m = Mex(b);
        A[l] = m;
        for (int i = l + 1; i + 1 <= N; i++)
            A[i] = A[i + 1];
        for (int i = N - (r - l) + 1; i <= N; i++)
            A[i] = 0;
        N -= (r - l);
    };

    if (*max_element(A.begin(), A.end()) == 0) {
        check(1, 2);
        check(2, N);
        check(1, N);
        print();
        return;
    }

    while (N >= 2) {
        int flg = 0;
        for (int i = 1; i <= N; i++) {
            if (A[i] == 0) {
                if (i != N) {
                    check(i, i + 1);
                    flg = 1;
                    break;
                }
                else {
                    check(i - 1, i);
                    flg = 1;
                    break;
                }
            }
        }
        if (!flg)
            check(1, N);
    }

    print();
}


int main() {
    freopen ("B.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
}

C - Serval and The Formula

Question

给定 $x, y$ ，需要找到一个非负数 $k \leq 10^{18}$ 满足 $(x + k) + (y + k) = (x + k) \oplus (y + k)$ 成立，若不存在则输出 $- 1$

Solution

异或是二进制下不进位的加法，所以 $a + b = a \oplus b ⟺ a & b = 0$

显然 $x = y$ 时无解

由于 $x, y \leq 10^{9}$ ，只要保证 $max (x, y) = k$ 的二进制下的低位有足够多的 $0$ ，就能保证 $(x + k) & (y + k) = 0$

而 $X = (1 << 50)$ 足够多了，我们求的 $k = X - max (x, y)$

Code

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

void solve() {
    ll x, y; cin >> x >> y;
    if (x == y) {
        cout << -1 << '\n';
        return;
    }
    ll k = (1ll << 50) - max(x, y);
    cout << k << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();

}

D - Serval and Kaitenzushi Buffet

Question

有一个传送带，上有 $n$ 盘子，每个盘子上有 $k$ 片寿司，第 $i$ 个盘子里的美味程度为 $d_{i}$

第 $i$ 分钟，第 $i$ 个盘子会到 Serval 面前

初始时寿司片计数器 $r = 0$ ，第 $i$ 分钟，他可以选择一个操作：

取下第 $i$ 盘寿司，收益加 $d_{i}$ ， $r$ 加 $k$
吃掉一片 $r - 1$
什么都不做， $r$ 不变

要求在 $n$ 分钟结束后， $r = 0$

Solution

先思考一个问题，其实第 $i$ 时刻取第 $d_{i}$ 盘是一个相对的概念

由于 $r$ 可以累加无上限，只需要到最后降到 $0$ 即可

我们假象在第 $i$ 盘寿司在大于等于 $i$ 时刻之后都可以拿起，在这个题中和只能在第 $i$ 时刻拿起是一样的

一种不是最优但是可行的方法是在 $n - k, n - (2 k + 1), n - (3 k + 2), \dots$ 处取下寿司，我们标记这些位置

根据之前的结论，在第 $i$ 的位置可以取下小于等于 $i$ 分钟的盘子

所以从头往后处理，当遇到一个标记时，找之前的价值最大的盘子取下，这个可以用一个堆实现

Code

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

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

int main() {
    freopen ("D.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();

    return 0;
}

E - Serval and Modulo

Question

已知长度为 $n$ 的数组 $a$ ，将各个元素对数字 $k$ 取模后，打乱顺序后得到数组 $b$

需要你求出 $k$ ，或者说明不存在这样的 $k$

Solution

大体想法肯定是枚举 $k$ ，但是发现 $k$ 的可能值很多，要考虑如何缩小 $k$ 的取值范围

$k | a_{i} - b_{i}$ 求和可以得到 $k | \sum a_{i} - \sum b_{i}$

所以我们只需要枚举 $\sum a_{i} - \sum b_{i}$ 的因子即可，这个的数量级大约在 $\sqrt{10^{10}} = 10^{5}$ ，但实际上最大只有 $2304$ ，所以总时间复杂度为 $O (2300 \times n)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int vis[1000005];
constexpr int INF = 1e9;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i] - b[i];

    if (sum == 0) {
        if (a == b) {
            cout << INF << '\n';
            return;
        }
        else {
            cout << -1 << '\n';
 
            return;
        }
    }

    vector<ll> factors;
    for (ll i = 1; i * i <= sum; i++) {
        if (sum % i == 0) {
            factors.push_back(i);
            if (i * i != sum) factors.push_back(sum / i);
        }
    }

    auto check = [&] (ll k) {
        // cout << k << '
        for (int i = 1; i <= n; i++) vis[a[i] % k] += 1;
        for (int i = 1; i <= n; i++) vis[b[i]] -= 1;
        int flg = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[a[i] % k] != 0 or vis[b[i]] != 0) {
                flg = 0;
                break;
            }
        }
        for (int i = 1; i <= n; i++) vis[a[i] % k] = 0, vis[b[i]] = 0;
        return flg;
    };

    for (ll &k : factors) {
        if (check(k)) {
            cout << k << '\n';
            return;
        }
    }

    cout << -1 << '\n';
}

int main() {
    // freopen ("E.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();

    return 0;
}