Codeforces Round #670 (Div. 2) 题解
[CF1406A] Subset Mex
提交地址：https://codeforces.com/contest/1406/problem/A
题目大意
给定一个非负整数构成的可重集合 $\{ a_1, a_2, \dots, a_n \}$，将其分成 $A, B$ 两个子集合（可以为空），求最大的 $\operatorname{mex}A+\operatorname{mex}B$。
数据范围：$1 \leq n, a_i \leq 100$。
题解思路
从 0 开始遍历每个非负整数。如果某个数字 $x$ 出现了不少于 2 次，则可以使 $A, B$ 中都包含 $x$，从而使 $\operatorname{mex}$ 值更大；如果 $x$ 没有出现，则 $A, B$ 中都不能包含 $x$，遇到第一个没有出现过的 $x$ 则应终止循环，因为此时 $\operatorname{mex}$ 值都已确定，且至少有一个集合的 $\operatorname{mex}$ 值为 $x$；如果 $x$ 只出现过 1 次，则应尽量将这样的 $x$ 都分入同一子集中，贪心地使该集合的 $\operatorname{mex}$ 尽量大，而另一子集的 $\operatorname{mex}$ 值就确定为 $x$ 了。
根据上述规则，设最小的出现次数小于 2 的非负整数为 $p$。如果 $p$ 一次都没出现，则两集合的 $\operatorname{mex}$ 值都为 $p$，答案为 $2p$；如果 $q$ 只出现了一次，则找到最小的没出现过的非负整数 $q$，一子集的 $\operatorname{mex}$ 值为 $p$，另一为 $q$，答案为 $p+q$。
时间复杂度为 $O(n)$。
代码
// Code by KSkun, 2020/9
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 105;
int T, n, cnt[MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
fill(cnt, cnt + MAXN, 0);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[x]++;
}
int val1 = -1, val2 = -1;
for (int i = 0; i <= 100; i++) {
if (cnt[i] == 0) {
if (val1 == -1) val1 = val2 = i;
else val2 = i;
break;
} else if (cnt[i] == 1) {
if (val1 == -1) {
val1 = i;
}
}
}
cout << val1 + val2 << endl;
}
return 0;
}[CF1406B] Maximum Product
提交地址：https://codeforces.com/contest/1406/problem/B
题目大意
给定一个长为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，求一个长为 5 的子序列 $a_{m_1}, a_{m_2}, a_{m_3}, a_{m_4}, a_{m_5} \ (1 \leq m_1 < m_2 < m_3 < m_4 < m_5 \leq n)$，使它们的乘积 $\prod\limits_{i=1}^5 a_{m_i}$ 最大。
数据范围：$1 \leq n \leq 10^5, |a_i| \leq 3 \times 10^3$。
题解思路
现场想的
想了一个 DP，状态 $f(i, j, k)$ 表示前 $i$ 个数字中选出 $j$ 个数，且 $a_i$ 包含在选出的数之内的情况下，乘积的最小值 $(k=0)$ 和最大值 $(k=1)$。DP 的转移需要讨论 $a_i$ 的正负，具体如下：
- $a_i = 0$：
- 对任意的 $j, k$，$f(i, j, k)=0$。
- $a_i > 0$：
- $f(i, j, 0) = \min\limits_{1 \leq p \leq i-1} \{ f(p, j-1, 0) \} \cdot a_i$；
- $f(i, j, 1) = \max\limits_{1 \leq p \leq i-1} \{ f(p, j-1, 0) \} \cdot a_i$。
- $a_i < 0$：
- $f(i, j, 0) = \max\limits_{1 \leq p \leq i-1} \{ f(p, j-1, 0) \} \cdot a_i$；
- $f(i, j, 1) = \min\limits_{1 \leq p \leq i-1} \{ f(p, j-1, 0) \} \cdot a_i$。
DP 转移中用到的 $\min$ 和 $\max$ 值均可在转移过程中动态维护，因此 DP 的复杂度为 $O(n)$，可以通过本题。
后来想的
写题解的时候才明白这题，选 5 个数乘积最大可以贪心做。
如果给出的数全为负数，选 5 个最大的负数即可。
如果给出的数全为负数或 0，则把 0 选上，结果直接是 0。
如果给出的数正负都有，那还可以分 5 正、3 正 2 负、1 正 4 负等情况讨论，均可用贪心做出相关方案。
代码
这里放的是现场写的代码，所以是 DP 做法。
// Code by KSkun, 2020/9
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int T, n;
LL a[MAXN], f[MAXN][6][2];
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
LL mn[6], mx[6];
mn[0] = mx[0] = 1;
f[1][1][0] = f[1][1][1] = mn[1] = mx[1] = a[1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= min(i, 5); j++) {
if (a[i] < 0) {
f[i][j][0] = mx[j - 1] * a[i];
f[i][j][1] = mn[j - 1] * a[i];
} else if (a[i] == 0) {
f[i][j][0] = f[i][j][1] = 0;
} else {
f[i][j][0] = mn[j - 1] * a[i];
f[i][j][1] = mx[j - 1] * a[i];
}
}
for (int j = 1; j <= min(i, 5); j++) {
if (i == j) mn[j] = f[i][j][0];
else mn[j] = min(mn[j], f[i][j][0]);
if (i == j) mx[j] = f[i][j][1];
else mx[j] = max(mx[j], f[i][j][1]);
}
}
cout << mx[5] << endl;
}
return 0;
}[CF1406C] Link Cut Centroids
提交地址：https://codeforces.com/contest/1406/problem/C
题目大意
给定一棵大小为 $n$ 的树，树可能有多个重心，求如何删一条边加一条边把树变成只有一个重心的树。
数据范围：$3 \leq n \leq 10^5$。
题解思路
画了几个例子玩了一下。树最多有两个重心，此时令两个重心分别为树根，它们最大的子树大小一定相等，且不可能有两个最大的子树。因此在一个重心最大的子树里拿掉一个叶子，接到另一个重心上，就构造出了只有一个重心的树。
因此，做法就是先把重心找出来，如果只有一个重心就随便删一条加一条，如果有两个则像上面那样做就行了。
时间复杂度为 $O(n)$。
代码
// Code by KSkun, 2020/9
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int T, n, siz[MAXN], dep[MAXN], C[2], C_ch_siz_mx; // centroid
vector<int> G[MAXN];
void dfs1(int u, int par) {
siz[u] = 1;
for (auto v : G[u]) {
if (v == par) continue;
dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
}
}
int dfs2_rt; // dfs2 global param
void dfs2(int u, int par) {
int ch_siz_mx = 0;
for (auto v : G[u]) {
if (v == par) continue;
dfs2(v, u);
ch_siz_mx = max(ch_siz_mx, siz[v]);
}
ch_siz_mx = max(ch_siz_mx, siz[dfs2_rt] - siz[u]);
if (ch_siz_mx < C_ch_siz_mx) {
C[0] = u; C[1] = 0; C_ch_siz_mx = ch_siz_mx;
} else if (ch_siz_mx == C_ch_siz_mx) {
C[1] = u;
}
}
pair<int, int> dfs3(int u, int par) {
if (G[u].size() == 1) return {par, u};
for (auto v : G[u]) {
if (v == par) continue;
return dfs3(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
C_ch_siz_mx = n;
C[0] = C[1] = 0;
dep[1] = 1;
dfs1(1, 0);
dfs2_rt = 1;
dfs2(1, 0);
if (C[1] == 0) { // single centroid
cout << 1 << " " << G[1][0] << endl;
cout << 1 << " " << G[1][0] << endl;
continue;
}
dfs1(C[0], 0);
pair<int, int> e_to_cut;
for (auto v : G[C[0]]) {
if (siz[v] == C_ch_siz_mx) {
e_to_cut = dfs3(v, C[0]);
break;
}
}
cout << e_to_cut.first << " " << e_to_cut.second << endl;
cout << C[0] << " " << e_to_cut.second << endl;
}
return 0;
}[CF1406D] Three Sequences
提交地址：https://codeforces.com/contest/1406/problem/D
题目大意
给定一个长为 $n$ 的序列 $a_1, a_2, \dots, a_n$，求两个序列 $b_1, b_2, \dots, b_n$ 和 $c_1, c_2, \dots, c_n$ 分别满足以下条件：
- 对于任意 $i$，$a_i = b_i + c_i$；
- 序列 $b_1, b_2, \dots, b_n$ 单调不降；
- 序列 $c_1, c_2, \dots, c_n$ 单调不增。
且要求最小化 $\max\limits_{1 \leq i \leq n} \{ \max \{ b_i, c_i \} \}$。
另有 $q$ 次操作，每次为对序列 $a_1, a_2, \dots, a_n$ 下标在 $[l, r]$ 范围内的数字加上一个值 $x$。求每次操作后的上述最小值。
数据范围：$1 \leq n, q \leq 10^5, |a_i| \leq 10^9$。
题解思路
当我们确定好了 $b_1$ 和 $c_1$ 满足 $b_1+c_1=a_1$ 时，要构造出满足条件的序列，则必有：
- $a_i – a_{i-1} > 0$时，$b_i – b_{i-1} = a_i – a_{i-1}$，$c_i – c_{i-1} = 0$；
- $a_i – a_{i-1} < 0$时，$c_i – c_{i-1} = a_i – a_{i-1}$，$b_i – b_{i-1} = 0$；
- $a_i – a_{i-1} = 0$时，$b_i – b_{i-1} = c_i – c_{i-1} = 0$。
由于 $b$ 序列和 $c$ 序列的单调性质，最小化的实际上是 $\max \{ b_n, c_1 \}$。根据上式，容易得到 $b_n = b_1 + \sum\limits_{i=2}^n \max \{0, a_i – a_{i-1} \}$。记 $K = \sum\limits_{i=2}^n \max \{0, a_i – a_{i-1} \}, x = c_1$，则 $b_1 = a_1 – x$，$b_n = a_1 – x + K$，要最小化 $\max \{ x, a_1 + K – x \}$。容易发现这个式子是一个有最小值的折线，最小值在 $x=\dfrac{a_1+K]{2}$处取到（如果能整除，不能则在附近的整数处取到）。
则先预处理出 $K$，很容易计算出最小值。
接下来考虑操作对最小值的影响。如果操作区间覆盖了 $a_1$，则 $a_1$ 需要加上一个 $x$。对于 $K$ 而言，由于 $K$ 通过差分值计算出，区间加只影响区间左右端点处的差分值，重新计算即可。单次重新计算的复杂度为 $O(1)$。
总时间复杂度为 $O(n+q)$。
代码
// Code by KSkun, 2020/9
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n, q;
LL a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = n; i > 1; i--) {
a[i] -= a[i - 1];
}
LL K = 0;
for (int i = 2; i <= n; i++) {
K += max(0ll, a[i]);
}
LL x = (a[1] + K) / 2;
cout << max(x, a[1] - x + K) << endl;
cin >> q;
while (q--) {
int l, r, qx;
cin >> l >> r >> qx;
if (l - 1 >= 1) {
K -= max(0ll, a[l]);
a[l] += qx;
K += max(0ll, a[l]);
}
if (r + 1 <= n) {
K -= max(0ll, a[r + 1]);
a[r + 1] -= qx;
K += max(0ll, a[r + 1]);
}
if (l == 1) a[1] += qx;
x = (a[1] + K) / 2;
cout << max(x, a[1] - x + K) << endl;
}
return 0;
}[CF1406E] Deleting Numbers
提交地址：https://codeforces.com/contest/1406/problem/E
题目大意
这是一个交互题。
交互器会首先给出一个正整数 $n$，你需要根据交互器的操作猜出一个在 $[1, n]$ 范围内的正整数 $x$。
交互器最开始有一个包含 $1 \sim n$ 所有数字的集合，支持的操作如下：
A m：查询当前集合中为 $m$ 的倍数的数字的个数；B m：查询当前集合中为 $m$ 的倍数的数字的个数，并删除所有 $m$ 的倍数，但要猜的数字 $x$ 不会被删除；C m：告诉交互器你猜出 $x$ 的值为 $m$。
数据范围：$1 \leq n \leq 10^5$，操作总次数不能超过 $10^4$。
题解思路
既然涉及到倍数，应该是数论题。考虑枚举每一个质数，试图找出 $x$ 的所有质因子及其个数。
求助万能的 Wolfram Alpha，我们可以知道 $10^5$ 以内的质数有 9592 个，如果每个质数都删一下，然后通过 A 操作查是不是还剩数字没删，显然会超过操作次数限制。
依然考虑从小到大枚举每一个质数，容易发现，每个数字总会在它最小的质因子处被删掉，删更大的质因子的倍数时不会把它计入。而对于 $x$ 来说，删每一个质因子的时候它都会被算进去，因此每次 B 操作删质因子时算一下不考虑 $x$ 会留下应该删掉多少数字，与实际查询到的倍数个数比较，如果不一致则说明 $x$ 包含该质因子。再枚举质因子的个数，通过 A 操作验证含有多少质因子即可。删质因子的复杂度为 $O(n)$，$x$ 最多有 7 个质因子（$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17=510 \ 510>10^5$），每个质因子最多有 $\log x$ 个，因此验证质因子个数的总复杂度为 $O(\log n)$。
最后需要找出最小的质因子，上面也说过了枚举每个质因子是不行的，我们想到了根号的复杂度平衡原理。记不大于 $n$ 的质数个数为 $m$，则把质数分成大小为 $\lfloor \sqrt{m} \rfloor$ 的块，在做上述操作的同时每删完一块内的质数用 A 1 求还剩下的数字数量，和不考虑 $x$ 的数量比较，检查这一块内是否包含 $x$ 的最小质因数。如果包含，就遍历块内的每一个质数，通过 A 操作检查是否为 $x$ 的质因数。如果是，再像上面一样检查质因数的个数。这一部分的复杂度为 $O(\sqrt{n}+\log n)$。
根据上面的分析，总的复杂度为 $O(n + 7\log n + \sqrt{n})$，这个复杂度是可以通过本题的。
需要注意边界条件，$n=1$ 时只有 $x=1$ 一种情况，特判一下。
代码
// Code by KSkun, 2020/9
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n;
bool is_prime[MAXN];
vector<int> primes;
void sieve(int n) {
fill(is_prime + 2, is_prime + n + 1, true);
for (int i = 2; i <= n; i++) {
if (is_prime[i]) primes.push_back(i);
for (auto p : primes) {
if (p * i > n) break;
is_prime[p * i] = false;
if (i % p == 0) break;
}
}
}
bool vis[MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> n;
if (n == 1) {
cout << "C 1" << endl; cout.flush();
return 0;
}
sieve(n);
int left = n, ans = 1, sqrt_n = sqrt(n);
bool min_prim_flag = false;
for (int i = 0; i < primes.size(); i++) {
int p = primes[i];
cout << "B " << p << endl; cout.flush();
int mul_cnt = 0, real_mul_cnt;
cin >> real_mul_cnt;
for (int i = p; i <= n; i += p) { // mark all multiples of i as deleted
if (!vis[i]) {
vis[i] = true; left--; mul_cnt++;
}
}
if (mul_cnt != real_mul_cnt) { // p is a factor of x
int res;
for (LL j = p; j <= n; j *= p) {
cout << "A " << j << endl; cout.flush();
cin >> res;
if (res != 1) break;
ans *= p;
}
}
if (((i + 1) % sqrt_n == 0 || i == primes.size() - 1) && !min_prim_flag) { // divide into sqrt(n) blocks
cout << "A 1" << endl; cout.flush();
int res;
cin >> res;
if (res != left) { // min factor in this block
for (int j = i - sqrt_n + 1; j <= i; j++) {
cout << "A " << primes[j] << endl; cout.flush();
cin >> res;
if (res == 1) { // min factor
for (LL k = primes[j]; k <= n; k *= primes[j]) {
cout << "A " << k << endl; cout.flush();
cin >> res;
if (res != 1) break;
ans *= primes[j];
}
min_prim_flag = true;
break;
}
}
}
}
}
cout << "C " << ans << endl; cout.flush();
return 0;
}