[ABC313] C~E 题解

C - Approximate Equalization 2

让所有的数字都尽量接近平均数，先算出平均数，然后把所有数字分成两份，一份要加，一份要减，因为平均数有余数，余数肯定给最大的几个，所以这样计算总共需要加减多少个，然后在加减里面取 \(\max\) 即可。

时间复杂度：\(O(n\log n)\)

#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int n, a[N];
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int s = 0, r;
    for(int i = 1; i <= n; i ++)
        cin >> a[i], s += a[i];
    r = s % n, s /= n;
    sort(a + 1, a + n + 1);
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n - r; i ++) {
        if(a[i] <= s)
            cnt1 += s - a[i];
        else cnt2 += a[i] - s;
    }
    for(int i = n - r + 1; i <= n; i ++) {
        if(a[i] <= s + 1)
            cnt1 += s - a[i];
        else cnt2 += a[i] - s - 1;
    }
    cout << max(cnt1, cnt2) << '\n';
    return 0;
}

D - Odd or Even

设前 \(k - 1\) 个数的和的奇偶性为 \(x\)，则使用 \(n - k + 1\) 次询问得到 \(A_{k\sim n}\) 异或 \(x\) 的奇偶性。

考虑得到 \(A_{1\sim k - 1}\) 异或 \(x\) 的奇偶性，考虑用别的位置的贡献消除 \(A_i\) 的贡献，由于 \(k < n\) 所以 \(A_{n - 1}\) 的贡献已经被算过了，不妨用 \(A_{n - 1}\) 消除贡献，可以考虑如下构造：a[n - 1] xor a[n] xor query，query 查询 \(\{j\in{[1, k -1]\wedge j\ne i}\vee j = [n - 1, n]\}\)，这样就可以得到 \(A_i \oplus x\) 的奇偶性，由于 \(k\) 是奇数，所以前 \(k\) 个数的奇偶异或 \(x\) 的异或和等于原值的异或和异或 \(x\)，也就是 \(A_k\)，将 \(A_k \oplus x\) 与 \(A_k\) 比较可得出 \(x\) 的奇偶性，然后全部数字异或 \(x\) 消除它的影响就是原数组了。

时间复杂度：\(O(nk)\)。

// Problem: D - Odd or Even
// Contest: AtCoder - AtCoder Beginner Contest 313
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-08-05 20:27:06

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
const int N = 2e5 + 10;

int n, k;
bool a[N];
int t[N], tmp[N], x;
int ask() {
    memcpy(tmp, t, sizeof t);
    sort(tmp + 1, tmp + k + 1);
    cout << "? ";
    for(int i = 1; i <= k; i ++) cout << tmp[i] << ' ';
    int x;
    cout << '\n' << flush;
    cin >> x;
    return x;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    iota(t + 1, t + k + 1, 1);
    for(int i = k; i <= n; i ++) {
        t[k] = i;
        a[i] = ask();
    }
    for(int i = 1; i < k; i ++) {
        t[i] = n - 1;
        a[i] = a[n] ^ ask() ^ a[n - 1];
        t[i] = i;
    }
    int sum = 0;
    for(int i = 1; i <= k; i ++) sum += a[i];
    sum &= 1;
    sum ^= a[k]; 
    for(int i = 1; i <= n; i ++)
        a[i] ^= sum;
    cout << "! ";
    for(int i = 1; i <= n; i ++) cout << a[i] << ' ';
    cout << '\n' << flush;

    return 0;
}

E - Duplicate

首先观察到如果有连续两个数字大于 \(2\)，则会无限循环，这样会让其中一个数字无限复制。

所以假设第 \(i\) 个位置之后的都已经被消除了，使用了 \(step\) 步，现在要消除第 \(i\) 个位置的字符，则它身后的字符会复制 \((step + 1)(s_i - 1)\) 次，这样迭代更新 \(step\) 直到只剩一个字符为止。

时间复杂度：\(O(n)\)。

int step = 0;
for(int i = n - 1; i; i --) {
    if(s[i] >= '2' && s[i - 1] >= '2') return cout << -1 << '\n', 0;
    step ++, step %= mod, step = ((s[i] - '0' - 1) * step % mod + step) % mod;
}