语法组月赛视频讲解

T1

矩形面积 $= d * h$

半圆面积 $= \frac{π \times r^2}{2}$

根据题目意思，可以知道，我们要求的两位数要尽可能的小，一位数尽可能的大。这样才能够保证差值最小。

对三个数字进行从小到大排序，因为题目要求两位数的十位不能为 $0$ ，所以要进行特殊判断。如果有一个 $0$ ，就需要放到两位数的个位，如果有两个 $0$ ，就需要保证两位数的十位为非 $0$ 的数字。

题目要求插入数字之后的最大值，所以我们尽可能的靠前插入，在插入的时候满足 $d >$ 当下遍历的数字即可。

如果发现都没有可插入的位置，就把 $d$ 放在数字串最后即可。

双指针遍历：由于 $a$ 数组是严格递增的， $b$ 数组是非递减的，可以利用双指针技术高效地检查 $b$ 中是否包含 $a$ 中的每个元素。
- 初始化两个指针 i 和 j，分别指向 $a$ 和 $b$ 的起始位置。
- 对于每个 $a_i$ ，在 $b$ 中寻找是否存在 $b_j = a_i$ 。如果存在，则不需要新增题目；否则需要新增一道题目。
- 由于 $b$ 是非递减的，可以跳过比当前 $a_i$ 小的 $b_j$ 值。
贪心匹配：通过双指针的贪心匹配，可以确保每个 $a_i$ 最多被检查一次，从而将时间复杂度优化到 $O(n + m)$ 。

$k > 1$ 的情况：
- 当 $k > 1$ 时，生成的数字 $y$ 可以表示为 $x$ 重复 $k$ 次。例如， $x=12$ ， $k=2$ 时， $y=1212$ 。
- 这种数字一定可以被 $x$ 和另一个由 $1$ 重复 $k$ 次组成的数（如 $11$ , $111$ , ..., 即 $\frac{10^{k \cdot \text{len}(x)} - 1}{10^{\text{len}(x)} - 1}$）整除，因此 $y$ 是合数。
- 结论：只要 $k > 1$ ， $y$ 一定是合数，直接输出 NO。
$k = 1$ 的情况：
- 此时 $y = x$ ，只需判断 $x$ 本身是否为质数。
- 需要单独处理 $x=1$ 的情况（ $1$ 不是质数）。
- 对于其他 $x$ ，判断是否为质数即可。

$k=0$ 时
- 根据贪心思路，易得将 $a, b$ 数组排序后两两对齐配对的结果最优。
$k=1$ 时
- 有一次免费机会，选择 $a$ 与 $b$ 中的任意一个都有可能，需要枚举选择最优。枚举免费机会 $O(n^2)$ ， $a$ 与 $b$ 中剩余部分依旧是两两对齐配对，计算当前方案 $O(n)$ ，整体为 $O(n^3)$
- 之前免费方案为 $a_i$ 与 $b_{j-1}$ ，其代价为 $c_1$ ，现在免费方案为 $a_i$ 与 $b_j(j <= i)$ ，其代价为 $c_2$ 。观察可以发现： $c_2=c_1-|a_{j-1}-b_j|+|a_{j-1}-b_{j-1}|$
- 之前免费方案为 $a_i$ 与 $b_{j-1}$ ，其代价为 $c_1$ ，现在免费方案为 $a_i$ 与 $b_j(j > i)$ ，其代价为 $c_2$ 。观察可以发现： $c_2=c_1-|a_{j}-b_j|+|a_{j}-b_{j-1}|$

与上第一个规律类似，提前预处理出 $a_i$ 与 $b_1$ 进行免费配对后的代价，再使用以上规律计算即可，可将最内层优化至 $O(1)$ ，总复杂度 $O(n^2)$

目前还没有评论...