mydcwfy's Blog

ARC Round#127

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

已改 ABCDE。

A

题意：记 $f(x)$ 表示 $x$ 十进制下前缀 1 的个数，给定 $n$，求 $\sum_{i = 1} ^ n f(i)$。$n\leq 10 ^ {15}$。

大概是数位 DP 模板题罢（

首先加上位数小于 $n$ 的位数的所有答案，容易发现可以预处理。

然后对于每一位考虑计算，假设前面 $n$ 的高位都是 1，如果当位为 0，那么这一位及更低的位都不可能出现前缀 1 了。

如果当位比 1 大的话，容易发现此时此位和低位的和已经可以计算了，而且和 $n$ 无关。具体的，其实就是所有 $t$ 位的答案。

时间复杂度 $O(\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LL solve(LL n)
{
	int bit = 0;
	while (qpow(10, bit) <= n) bit ++;
	LL cur = 0;
	for (int i = 0; i < bit; ++ i) cur += qpow(10, i);
	LL res = 0;
	for (int i = 1; i <= bit - 1; ++ i) res += a[i];
	for (int i = 1, flag = true; i <= bit; ++ i)
	{
		if (n < qpow(10, bit - i)) break;
		flag &= n < 2 * qpow(10, bit - i);
		n %= qpow(10, bit - i);
		if (!flag) return res + a[bit - i + 1];
		if (flag) res += (n + 1);
	}
	return res;
}

B

题意：给定 $n, l$，需要构造 $3n$ 个长度为 $l$ 的字符串，满足 $\forall i\in [1, l]$，$3n$ 个字符串中 $s_i$ 是 0, 1, 2 的各占 $n$ 个，并且不存在两个字符串相同。另外需要保证字典序最大的字符串字典序最小。$l\leq 15, 3n\leq 3 ^ l$。

容易发现我们只需要构造开头为 2 的 $n$ 个长度为 $l$ 的字符串，按序推一下就可以相应的得到开头为 0 和 1 的字符串了。

那么现在问题就是我们需要 $n$ 个字符串使得字典序最大的最小，且不存在两两相同。直接 3 进制拆分即可，当然直接模拟也可以。

C

题意：有 $1\sim 2 ^ n - 1$ 的数二进制转换后按照字典序排列，问第 $x$ 个是哪个数。$x$ 和输出的数都使用二进制。$n\leq 10 ^ 6$。

首先考虑 $n = 3$ 的序列：1, 10, 100, 101, 11, 110, 111，一共有 7 个。注意到第二位的分布：第一个没有后面的位数，$2\sim 2 ^ {n - 1}$ 第二位是 0，$2 ^ {n - 1} - 1\sim 2 ^ n - 1$ 的第二位是 1。

注意到我们确定了第二位后，我们可以递归下去处理后面的位数。递归的方式如下：

  1. 没有后面的位数，直接退出。
  2. 第二位是 0，对 $x$ 减 1，然后递归。
  3. 第二位是 1，对 $x$ 减 $2 ^ {n - 1}$，然后递归。

注意到 $x$ 是二进制给出的，也就是说减 $2 ^ {n - 1}$ 是好做的，直接删除首位。但是减 1 没有好办法，但是我们发现暴力的复杂度是正确的，因为每在 $t$ 位（从低到高从 0 编号）退 1 的话，过 $O(2 ^ t)$ 次之后才可能再次贡献。也就是减 $n$ 次的复杂度是 $O(n)$ 的。

最后考虑如何判断第二位是什么。容易发现减完 1 / $2 ^ {n - 1}$ 之后为 0 了，直接退出就可以处理上述的第一种情况。另外，如果 $x = 2 ^ {n - 1}$，也可以直接退出。判断为 0 的方法就是维护最后一个非 0 位即可。

时间复杂度 $O(n)$。细节 yy 一下就差不多了（

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
std::string s, res = "1";
 
int main()
{
	std::cin.tie(0)->sync_with_stdio(false);
	std::cin >> n >> s;
	s = std::string(n - s.size(), '0') + s;
	for (int i = 0, j = n - 1; i < n; ++ i)
	{
		if (i == n - 1) break;
		while (j >= i && s[j] == '0') -- j;
		if (s[i] == '1' && j == i) {
			res += '0', res += std::string(n - i - 2, '1');
			break;
		} else if (s[i] == '1') {
			res += '1';
			continue;
		}
		s[j] = '0';
		while ((++ j) < n) s[j] = '1';
		j = n - 1;
		while (j >= i && s[j] == '0') -- j;
		if (j == i - 1) break;
		res += '0';
	}
	std::cout << res << '\n';
	return 0;
}

D

题意：给定两个长度为 $n$ 的数组 $a, b$，求：

$n\leq 2.5\times 10 ^ 5$，$a_i, b_i < 2 ^ {18}$。

看题解其实感觉比较板，但是赛时 C 花了太久了，几乎没怎么想就 vp 结束了。

容易发现我们肯定是需要知道什么时候 $a_i\oplus a_j$ 小，什么时候 $b_i\oplus b_j$ 小。如果找到他们最高的不同位就好做了，我们判断一下就好了。又发现 $a_i\oplus a_j$ 和 $b_i \oplus b_j$ 最高的不同位就是 $a_i\oplus b_i\oplus a_j\oplus b_j$ 的最高位。

现在我们就可以把 $i, j$ 分离，令 $c_i = a_i\oplus b_i$，我们就是找 $c_i\oplus c_j$ 的最高不同位。现在我们比较 $c_i, c_j$ 的最高位是 0 还是 1，都是 0 的我们考虑递归，都是 1 的同理。也就是说只需要处理 $c_i, c_j$ 最高位不同的情况，也就是现在我们已经能区分 $a_i\oplus a_j$，$b_i\oplus b_j$ 的大小关系了。

我们考虑把数按照 $c_i$ 的最高位和 $a_i$ 的最高位分成 4 类。这样很容易区分出哪些是 $a_i\oplus a_j$ 更小，哪些是 $b_i\oplus b_j$ 更小。

现在我们已经去除了 $\min$，只需要考虑给定一个数组，就两两异或和。拆位贡献可做到 $O(n\log a)$。

最后分析复杂度，考虑每一个 $(a_i, b_i)$ 的 std::pair，会被使用 $O(\log a)$ 次，每次使用都是 $O(\log a)$ 的复杂度，时间复杂度 $O(n\log ^ 2 a)$。

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
LL calc(std::vector<int> v1, std::vector<int> v2, int *a)
{
	if (v1.empty() || v2.empty()) return 0;
	static int cnt1[18], cnt2[18];
	for (int i = 0; i < 18; ++ i) cnt1[i] = cnt2[i] = 0;
	for (int i : v1)
		for (int bit = 0; bit < 18; ++ bit)
			if (a[i] >> bit & 1) cnt1[bit] ++;
	for (int i : v2)
		for (int bit = 0; bit < 18; ++ bit)
			if (a[i] >> bit & 1) cnt2[bit] ++;
	LL res = 0;
	int n = v1.size(), m = v2.size();
	for (int bit = 0; bit < 18; ++ bit)
		res += ((LL) cnt1[bit] * (m - cnt2[bit]) + (LL) cnt2[bit] * (n - cnt1[bit])) << bit;
	return res;
}

LL solve(std::vector<int> v, int bit)
{
	if (v.size() <= 1) return 0;
	if (bit < 0) return calc(v, v, a) / 2;
	std::vector<int> to[2][2];
	for (int i : v)
		to[c[i] >> bit & 1][a[i] >> bit & 1].push_back(i);
	LL res = calc(to[0][0], to[1][0], a) + calc(to[0][1], to[1][1], a)
		+ calc(to[0][0], to[1][1], b) + calc(to[0][1], to[1][0], b);
	for (int i : to[0][1]) to[0][0].push_back(i);
	for (int i : to[1][1]) to[1][0].push_back(i);
	return res + solve(to[0][0], bit - 1) + solve(to[1][0], bit - 1);
}

E

给定一个 $A + B$ 的序列，有 $A$ 个 1 和 $B$ 个 2，初始有一个空的集合 $s$。你需要对 $A$ 个 $1$ 分配一个 $[1, A]$ 的值使得不存在两个位置相等。对于每一个 1，你需要向 $s$ 中插入分配的值；否则你需要删除集合中最大的元素。问最后得到的集合 $s$ 有多少种可能，答案对 998244353 取模。$A\leq 5000$，$ B < A$。

一个显然的想法是对每一个集合 $s$，判断其是否合法。

假设能得到的最大的集合为 $t$，则集合合法的充要条件是 $s\leq t$（严格小于等于）。

证明：首先证明其必要性。容易发现如果不满足的话肯定是无法构造的，因为我们已经构造了最大的集合了。

然后证明其充分性。没看懂题解，但似乎是可以感性理解的（？

有了上面的结论，我们先要找到最大的集合。容易发现我们肯定把更小的放前面，这样被删除的也偏小，留下的就自然更大了，于是就是在第 $i$ 个 1 的位置放 $i$ 即可得到最大的集合。

得到最大的集合过后，我们相当于是求合法的序列，有两个限制：$x_i < x_{i + 1}$，$x_i\leq a_i$。这个显然是可以 $O(na)$ DP 完成的。

时间复杂度 $O(A ^ 2)$，代码不放了。