[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;
}