Codeforces Round #670 (Div. 2) 题解

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

参考资料



发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据