小编点评

**代码解析：** **A. Unit Array 秒切题：** ```python def solution(nums): # 定义两个变量，存储右边界和左边界 left = 0 right = len(nums) # 循环直到左右边界相等 while left < right: # 计算中间点 mid = (left + right) // 2 # 如果中间点的元素大于右边界，则向左移动 if nums[mid] > right: left = mid + 1 # 如果中间点的元素小于左边界，则向右移动 else: right = mid - 1 # 返回中间点 return mid ``` **B. Maximum Strength题目：** ```python def solution(nums): # 定义三个变量，存储 left、right 和 mid left = 0 right = len(nums) mid = 0 # 循环直到左右边界相等 while left <= right: # 计算中间点 mid = (left + right) // 2 # 计算左半部分的最大元素 left_max = max(nums[:mid]) # 计算右半部分的最大元素 right_max = max(nums[mid:]) # 返回最大力量 result = abs(left_max - right_max) if result > result: result = result # 更新左右边界 left = mid + 1 right = mid - 1 # 返回最大力量 return result ``` **C. Survey in Class：** ```python def solution(nums): # 遍历数组，计算每个元素的最小最大值 left_max = max(nums) right_min = 0 # 遍历数组，计算每个元素的最小最大值 for num in nums: left_max = max(left_max, num) right_min = min(right_min, num) # 返回最小最大值之差 return abs(left_max - right_min) ``` **D. MEX of LCM：** ```python def solution(nums): # 定义三个变量，存储右边界、左边界和 LCM right = len(nums) left = 0 lcm = nums[0] # 循环直到左右边界相等 while left <= right: # 计算中间点 mid = (left + right) // 2 # 如果中间点的 LCM 与右边界相等，则向右移动 if lcm == right: right = mid - 1 # 如果中间点的 LCM 与左边界相等，则向左移动 elif lcm == left: left = mid + 1 # 更新 LCM lcm = max(lcm, nums[mid]) # 返回 LCM return lcm ```

正文

CF1834

Virtual Contest 做了 5 道题，非常不错。

A.Unit Array

秒切题，判断个数，然后判断一下奇偶即可。

提交：https://codeforces.com/contest/1834/submission/211190220

B.Maximum Strength

题目描述

每一种材料的力量由一个十进制整数表示。

对于一个武器，由两种材料构成。假如第一种材料的力量为 \(X = \overline{x_1x_2 \dots x_n}\)，第二种材料的力量为 \(Y = \overline{y_1y_2 \dots y_n}\)，那么这个武器的力量为 \(\sum_{i = 1}^n |x_i - y_i|\)，也就是 \(|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|\)。

如果两个数字长度不一样，则要将短的数字用前导零补成相同长度。

现在，你拥有无数个力量在 \([L, R]\) 中的材料。你想要选出两个材料做出一个力量最大的武器。请你求出你设计出的武器力量的最大值。

题解

找到第一个不同的地方，其他地方全部填 \(|9 - 0|\) 即可。

大数填 0，小数填 9，这样一定满足在区间内。

提交：Submission #211191108 - Codeforces

C.Game with Reversing

题目描述

你有两个长度为 \(n\) 的序列 \(S, T\)。

你将不断重复以下步骤直到两个序列相等：

1. 在 \(S\) 或者 \(T\) 中任意选择一个数字，然后修改为另一个数字。如果此时序列相等，则结束操作，否则进入操作 2。

2. 任意反转一个序列。如果此时序列相等，则结束操作，否则重复操作 1。

注意：操作 1 和操作 2 都计入操作次数中。

你需要输出最小化的操作次数。

解题

正序和逆序分别讨论一下，取 \(\min\) 即可。

设 \(icnt\) 表示正序不同的个数，\(rcnt\) 表示逆序不同的个数。

那么 \(ans = \min(2 \times icnt - icnt \% 2, 2 \times rcnt - (rcnt - 1) \% 2)\)。

提交：https://codeforces.com/contest/1834/submission/211198802

D.Survey in Class

对于每一个学生的学习集合，答案是 \(2 \times \max(|S_1| - |S_1 \cap S_2|)\)。

\(O(n \log n)\)

考虑使用树状数组维护线段，从左向右扫一遍。

\(O(n)\)

考虑两条线段的关系，三种：

• 左边

• 相交

• 右边

对于每一个 \(S_1\)，我们需要最小化 \(|S_1 \cap S_2|\)，所以对于三种情况，我们维护三个线段：

• 右端点最左

• 最短

• 左端点最右

分别判断即可。

提交：Submission #211192375 - Codeforces

E.MEX of LCM

我考场上的做法

考虑只有 \(O(n^2)\) 个取值，那么 \(mex\) 一定 \(\le n^2\)。所以我们限制了答案的上界，设为 \(U\)。

实际上有更紧的上界，根据：CF1834E MEX of LCM 题解 - LCTTTTTTTTTTT - 洛谷博客，\(U\) 可以 \(= 4256233\)。

考虑对于一个固定的右端点，其左端点与其匹配的 \(lcm\) 是单调的，并且不同的数量在 \(O(\log U)\) 。

考虑每一次变化 \(lcm\) 至少 \(\times 2\)。

所以考虑用一个 set 维护。

同时，再用一个 set 维护所有出现过的 lcm （考虑是 \(O(n \log U)\) 个，空间没问题）

所以总复杂度为 \(O(n \log V \log U \log \log U)\)。

提交：Submission #211194246 - Codeforces

还有的思路

考虑每一个左端点，可以二分找 lcm 的分界，当值大于上界的时候退出。

用桶或者什么东西操作一下即可。

复杂度为 \(O(n \log U \log n)\)。

然而还有玄学优化，参考：出错了 - 洛谷