mydcwfy's Blog

ARC Round#116

Posted on
Symbols count in article: 3.5k Reading time ≈ 8 mins.

All Accepted。

A

题意：给定一个数 $n$，判断 $n$ 的奇因数多还是偶因数多。$T(T\leq 2\times 10 ^ 5)$ 组数据，$n\leq 10 ^ {18}$。

容易发现如果 $n$ 是奇数肯定是奇因数多，否则如果 $n$ 是 4 的倍数，那么如果 $d$ 是奇因数，那么 $2d, 4d$ 都是偶因数，这样 $n$ 的偶因数多。否则一样多。

B

题意：给定一个序列 $A$，问所有非空子序列 $B$ 的 $\max(B)\times \min(B)$ 的和。$n\leq 2\times 10 ^ 5$，答案对 998244353 取模。

首先排除我们只选一个数的贡献，假设我们确定最大值和最小值，那么可以得到可以计算的次数为 $2 ^ {r - l}$。注意到 $r, l$ 是分开的，这个可以使用前缀 / 后缀和优化，比如我们记录 $\sum_{i = l} ^ n 2 ^ la_i$ 就可以 $O(\log p)$ 或者 $O(1)$ 计算单个最小值的贡献了。时间复杂度 $O(n\log p)$ 或者 $O(n)$。

C

题意：给定 $n, m$，问有多少个长度为 $n$ 的序列满足 $a_i | a_{i + 1}$ 并且 $1\leq a_i\leq m$。$n, m\leq 2\times 10 ^ 5$，对 998244353 取模。

考虑我们枚举 $a_n$，那么考虑对每个质因数的次数拆开看，相当于是找一个不减的序列，末项已经确定了。容易发现这就是一个插板法，答案为 $\displaystyle \binom {n + t - 1}{n - 1}$。

直接计算，复杂度 $O(m\log n)$（要分析成 $O(m\sqrt n)$ 没问题罢，但是感觉就是 $\log$ 的）。

D

题意：给定 $n, m$，问有多少个长度为 $n$ 的序列和为 $m$ 并且异或和为 0。对 998244353 取模。$n, m\leq 5000$。

直接考虑按位 DP，注意每一位出现的次数必须为偶数，这样背包 + 组合数学可以做到 $O(n m\log m)$。另外还可以发现每一次操作完后末位必须为 0，否则肯定不合法。同时我们可以把最后一位去掉，可以做到 $O(nm)$。（好像原来也是 $O(nm)$ 的？

E

这个题之前的题似乎都比较一眼（

题意：给定一棵 $n$ 个点的树，你可以选定 $k$ 个关键点，使得 $\max_{i = 1} ^ n \min_{j = 1} ^ k \text{dis}(i, node_j)$ 最小。$n\leq 2\times 10 ^ 5$。

场上想到了二分 + 树形 DP，但是剩下的写不出来 /ll

看到这个最大最小，果断二分。

相当于我们已经给定了一个距离了，问至少要有多少个关键点。

注意到一棵子树只会对外面产生的影响由两种：一是关键点距离根距离 $<d$，那么会对外面的一些选择产生影响。否则就是至少需要距离根不超过某一值的关键点。

注意到不同子树之间合并是容易的，反正可能细节比较多就是了。我直接贴代码。从 Um_nik 的写法中得到的，正数表示第一种情况，否则表示第二种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x, int fa = 0)
{
	f[x] = add[x] = 0;
	for (int v : g[x]) {
		if (v == fa) continue;
		dfs(v, x);
		f[x] += f[v];
		if (add[x] > add[v]) std::swap(add[x], add[v]);
		if (add[x] <= 0 && add[v] > 0 && add[v] - add[x] <= dis) add[x] = add[v];
	}
	if (add[x] == -dis) f[x] ++, add[x] = 1;
	else if (add[x] > 0) add[x] ++;
	else add[x] --;
}

bool check() { return dfs(1), f[1] + (add[1] < 0) <= k; }

F

题意：有 $n$ 个序列，每个序列长度为 $m_i$，两个人轮流拿数，每次可以把一个长度不为 1 的序列的首尾任意一个数拿走。在两个人都使用最优走法时（先手想让剩的 $n$ 个数和最大，后手相反），问剩的数的和。$n, \sum m\leq 2\times 10 ^ 5$。

假设所有数列的长度都是奇数，我们想一想该如何选。容易发现此时后手更有主动权，因为如果后手想要维持保留最终点的话时很容易做到的，而他也可以不这么选择。也就是说，如果先手选择的左半，后手也可以选择左半，此时后手肯定希望选到 $a(mid + 1)$，因为他不可能选到 $a(mid + 2)$（先手可以和他平衡），既然选择了删除左半，肯定是希望选到 $a(mid + 1)$。而如果先手先删除右半，那么后手就有机会选择 $a(mid - 1)$。这样的话，先手有能力去掉 $a(mid - 1)$ 和 $a(mid + 1)$ 中的较小值的，剩下的再和 $a(mid)$ 取 $\min$。这样的话，最后能取到的一定是 $\min(a(mid), \max(a(mid - 1), a(mid + 1)))$。

然后考虑有多个序列的。前面说到后手更有主动权，那么最开始的后手肯定并不希望自己成为先手，而这个又是可以实现的，就是和先手在同一条序列上操作。容易发现操作完后先后手顺序不变，所以直接简单的把所有加起来即可。

然后考虑有偶数情况的。注意到偶数长度的情况先手占有主动权。我们发现先手可以选择删前还是删后就可以变成一个偶数的情况了，而此时原来的先手就占有主动权了。删前还是删后是由删了过后偶数情况所决定的。

最后考虑有多个偶数情况的。容易发现由于单个序列先手有主动权，那么肯定先后手轮流先取偶数的序列。最后再考虑去玩过后，原来的先手有没有变成后手，两次的贡献不同。

时间复杂度 $O(n + \sum m)$。

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
int main()
{
	std::cin >> n;
	for (int i = 1, tot; i <= n; ++ i)
	{
		scanf("%d", &tot);
		sum += tot - 1;
		a[i].resize(tot);
		for (int &x : a[i]) scanf("%d", &x);
	}
	std::vector<int> vec;
	for (int i = 1; i <= n; ++ i)
		if (a[i].size() & 1) {
			int mid = a[i].size() / 2;
			if (a[i].size() == 1) res += a[i][mid];
			else if (!(sum & 1))
				res += std::min(a[i][mid], std::max(a[i][mid - 1], a[i][mid + 1]));
			else res += std::max(a[i][mid], std::min(a[i][mid - 1], a[i][mid + 1]));
		} else {
			int mid = a[i].size() / 2;
			if (a[i].size() == 2)
				res += std::min(a[i][mid - 1], a[i][mid]), vec.push_back(abs(a[i][mid] - a[i][mid - 1]));
			else {
				int v1 = std::max(a[i][mid], std::min(a[i][mid - 1], a[i][mid + 1])),
					v2 = std::max(a[i][mid - 1], std::min(a[i][mid - 2], a[i][mid]));
				if (!(sum & 1))
					v1 = std::min(a[i][mid], std::max(a[i][mid - 1], a[i][mid + 1])),
					v2 = std::min(a[i][mid - 1], std::max(a[i][mid - 2], a[i][mid]));
				res += std::min(v1, v2), vec.push_back(abs(v1 - v2));
			}
		}
	int mid = (vec.size() + 1) / 2;
	std::sort(vec.begin(), vec.end(), std::greater<int>());
	for (int i = 0; i < (int) vec.size(); ++ i)
		if (!(i & 1)) res += vec[i];
	std::cout << res << '\n';
	return 0;
}