Codeforces Round 1011 (Div. 2) (opens new window)

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\le l < r \le|a|)$ 用单个数 $mex(a_l,a_{l+1},\cdots,a_r)$ 替换 $l,r$ 区间里面的数

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

Solution

我的解法比较麻烦

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

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

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

每次从头找，如果发现一个 $0$ 的位置为 $i$，那么让 $i$ 和 $i$ 边上的元素做一次 $mex$ 操作即可消除 $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\le 10^{18}$ 满足 $(x+k)+(y+k)=(x+k)\oplus (y+k)$ 成立，若不存在则输出 $-1$

Solution

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

显然 $x=y$ 时无解

由于 $x,y\le 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-(2k+1),n-(3k+2),\cdots$ 处取下寿司，我们标记这些位置

根据之前的结论，在第 $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;
}