mydcwfy's Blog

CF Round Global#21

Posted on
Symbols count in article: 4.1k Reading time ≈ 9 mins.

还算没有掉分……主要是 E 过于板子的功劳。

赛时 ABCDE Accepted，Score：5682，Rank #412。

改题进度：ABCDEF Accepted。

A

题意：给定长度 $n$ 的数组 $a$ 和一个数字 $z$，每次可以选一个 $a$ 中的 $x$，$x\leftarrow x|z$，$z\leftarrow x\odot z$，求 $a$ 最大值的最大值。

容易发现因为 $z$ 不可能增加，最多操作一次。判断一下即可。

B

题意：给定序列 $a$，每次可以选定 $[l, r]$ 使得他们值都变为原来的 $\text{mex}$，求变为 0 的最少次数。

首先答案肯定不超过 2，因为可以两次操作整个数组，一定都变为 0。

如果都是 0，答案为 0。

如果不含 0 的区间只有 1 个，那么操作这个区间即可，答案为 1。

否则答案为 2。

C

给定两个数组 $a, b$，再给定 $t$，每次可以把一个被 $t$ 整的数 $x$，变为 $t$ 个 $\dfrac xt$ 插入在原位置，或者把 $t$ 个相邻的 $x$ 合并为一个 $xt$。问 $a$ 能否变成 $b$。

容易发现操作可逆，那么我们可以先把所有的操作 1 做了，然后再做操作 2。那么问题可以转化成 $a, b$ 经过操作 1 能否相同。

一个显然的想法是我们一直操作下去直到无法操作。暴力拆分肯定不好，我们考虑维护极长的相同的数的连续段，这样就可以做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
std::vector<PIL> get(int n)
{
	std::vector<PIL> res;
	for (int i = 1, x; i <= n; ++ i)
	{
		scanf("%d", &x);
		int t = 1;
		while (x % m == 0) t *= m, x /= m;
		if (res.size() && res.back().first == x) res.back().second += t;
		else res.push_back({x, t});
	}
	return res;
}
 
void work()
{
	int n, k;
	std::cin >> n >> m;
	auto v1 = get(n);
	std::cin >> k;
	auto v2 = get(k);
	if (v1.size() != v2.size()) return puts("NO"), void();
	for (int i = 0, ed = v1.size(); i < ed; ++ i)
		if (v1[i].first != v2[i].first || v1[i].second != v2[i].second)
			return puts("NO"), void();
	puts("YES");
}

D

题意：给定一个排列 $a$，$i, j(i < j)$ 之间有连边当且仅当 $a_i, a_j$ 都是 $a_{i\to j}$ 的极值。求 1 到 $n$ 的最短路。$n\leq 2.5\times 10 ^ 5$，$ \sum n\leq 5\times 10 ^ 5$。

考虑观察性质，假设 1 的位置是 $p$，那么连边不可能跨过 $p$，也就是说一定会导致经过 1 一次。同样会经过 $n$ 所在位置 $q$ 一次。而我们又发现，$p, q$ 之间又有连边，这样我们就可以计算 $[1, p]$ 的距离，$[q, n]$ 的距离，加上 $[p, q]$ 之间距离为 1，于是可以递归。（$p, q$ 可以交换）

于是用 ST 表查询区间最大值、最小值的位置即可，时间复杂度 $O(n\log n)$，可以优化到 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void work()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	init();
	std::function<int(int, int)> solve = [&](int l, int r) {
		if (l == r) return 0;
		int id1 = qmin(l, r), id2 = qmax(l, r);
		if (id1 > id2) std::swap(id1, id2);
		// std::cout << l << ' ' << r << ' ' << id1 << ' ' << id2 << '\n';
		return solve(l, id1) + solve(id2, r) + 1;
	};
	printf("%d\n", solve(1, n));
}

E

题意：在无限的网格上，从 0 开始标号，前 $n$ 列的 $[0, a_i - 1]$ 都是黑的，其余都是白的，最开始有一个棋子在 $(0, 0)$，每次可以移动在 $(i, j)$ 的棋子，会分裂成两个棋子到 $(i + 1, j)$ 和 $(i, j + 1)$ 的位置。求最少操作次数使得黑的都没有棋子，对 $10 ^ 9 + 7$ 取模。$n, a_i\leq 2\times 10 ^ 5$，$a$ 单调不升。

考虑每一个黑色位置的贡献。$(i, j)$ 这个位置的贡献可以由 $(i - 1, j)$ 和 $(i, j - 1)$ 贡献而来。注意到如果这两个位置合法，那么一定都是黑色的，因为 $a$ 单调不升。

这就是组合数，容易得到他为 $\binom{i + j}i$，那么我们可以写出如下答案式子：

时间复杂度 $O(na)$，无法通过。看看后面这个式子应该由比较好的性质。

记 $t = i, m = a_i - 1$，则我们需要计算的就是 $\sum_{j = 0} ^ m \binom{j + t}{t}$。如果对组合数学比较熟悉的话马上就可以得到这个式子其实等于 $\binom{m + 1 + t}{t + 1}$。

于是我们就得到了最终的答案：

直接计算，时间复杂度 $O(n)$。

F

题意：给定所有三元组 $(x, y, z)$ 是否满足 $d(x, y) = d(y, z)$，要求构造一棵树使得满足上面所有条件，或报告无解。$n\leq 100$。

有一个关键性质：如果我们已经知道了某一条树边，我们马上就可以还原出整个树。

具体的，我们考虑得到 $x$ 和他的父亲 $fa$，我们可以还原出所有 $v$，他们一定满足 $dis(x, v) = dis(fa, x)$。

我们如果不知道边的话，直接考虑枚举 1 和某个点的树边，按照这个暴力计算，即可得到一棵树。

然后考虑如何判断该树是否合法。直接暴力 $O(n ^ 3)$ Floyd 即可。

总时间复杂度 $O(n ^ 4)$，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void dfs(int x, int frm)
{
	dis[x][frm] = dis[frm][x] = 1;
	vis[x] = true;
	for (int v = 1; v <= n; ++ v)
		if (!vis[v] && mp[frm][x][v]) edg.push_back({v, x}), dfs(v, x);
}
 
bool check(int v)
{
	for (int i = 1; i <= n; ++ i) vis[i] = false;
	edg.assign(1, {1, v});
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j) dis[i][j] = (n + 1) * (i != j);
	vis[1] = vis[v] = true, dfs(v, 1), dfs(1, v);
	for (int i = 1; i <= n; ++ i)
		if (!vis[i]) return false;
	for (int k = 1; k <= n; ++ k)
		for (int i = 1; i <= n; ++ i)
			for (int j = 1; j <= n; ++ j)
				chkmin(dis[i][j], dis[i][k] + dis[k][j]);
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j)
			for (int k = i + 1; k <= n; ++ k)
				if ((dis[i][j] == dis[j][k]) ^ mp[i][j][k])
					return false;
	return true;
}
 
void work()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i)
		for (int j = i + 1; j <= n; ++ j)
		{
			static char buf[N];
			scanf("%s", buf + 1);
			for (int k = 1; k <= n; ++ k) mp[i][k][j] = buf[k] & 1;
		}
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j) mp[i][j][i] = true;
	for (int i = 1; i <= n; ++ i)
		for (int j = i + 1; j <= n; ++ j)
			for (int k = 1; k <= n; ++ k)
				mp[j][k][i] = mp[i][k][j];
	for (int v = 2; v <= n; ++ v)
	{
		if (!check(v)) continue;
		puts("Yes");
		for (auto [u, v] : edg) printf("%d %d\n", u, v);
		return;	
	}
	puts("No");
}