「题解」Codeforces Round 1016 (Div.3)

Mohao2025/4/9大约 3 分钟

A. Ideal Generator

这种题我是身经百战，见得多了！题面看都不看一眼的，直接对着样例一顿输出。要不是卡了下又能 0min 过题了捏😋

B. Expensive Number

本题的重点在于不能除零……大概。
因此我们为了让这个东西尽可能小，必须要把后缀零删去，同时考虑到可以保留前缀零，因此我们的答案就是后缀零的个数加上最后一个非零数字之前的非零数字的个数。

首先我们可以考虑最简单的情况：
当 $k = 1$ 时，我们只需要考虑 $x$ 是否为素数即可。接着我们可以考虑一下 $k$ 不为 $1$ 的情况：如果 $x$ 只有一位
那么除了 $11$ 之外，无论 $k$ 多大总有
因数 $11, 111, 111, \ldots$ 以此类推，考虑 $x$ 两位的情况，总有因数
$101, 10101, \ldots$ ，所以我们得出结论：
当 $k \ge 2$ 时，有且仅有 $x=11$ 时题设
成立。

再实现时需要注意一点：考虑到本题 $x \le 10^9$ ，我们直接用试除法在 $O(\sqrt n)$ 内判断素数即可。观察到赛后有一些人
因为预处理了素数而导致 MLE 或者 TLE。。

D. Skibidi Table

一眼递归/分治。按照题意模拟即可。

E. Min Max MEX

笑点解析：System Testing 1984ms

首先我们看到这个题目的第一眼就是二分，二分
$x$ 时，统计数组中 $\text{MEX}$ 为 $x$ 的子数组的个数
然后再与 $k$ 判断即可。

特别需要注意的一点就是在计算 $\text{MEX}$ 的时候需要注意一些技巧：
我们遍历数组的时候，每次把小于 $x$ 的元素加入一个集合
如果这个集合的大小为 $x$ 的话，那么就证明这段子数组的
$\text{MEX}$ 为 $x$ 。然后清空即可。

我们发现被 hack 的人大部分没采用此种优化，而是
直接一股脑地把元素直接加进去，然后判断最大的元素
是否为 $x$ 以及元素的个数是否为 $x$ ，这显然会造成
很大的损耗。

还有一部分人没有使用 set 而是使用了 unordered_set,
但是 unordered_set 据说可以构造数据使得 clear() 的
时间复杂度退化成 $O(n^2)$ ，所以有些人也不幸的被卡了捏

哎哎，明明我在代码风格指北中说了像这种最大值确定的集合而且范围可以接受的，应该用随机存取容器，比如 vector 的，但是忘了捏。差点坠机

F. Hackers and Neural Networks

感觉……这个题目好像比前几题简单……
这题也就是题面长点而已～杂鱼杂鱼

考虑输出 $-1$ 的情况：当且仅当 $\exists \ j \in [1, m],
\forall \ i \in [1,n],\
a_{j} \ne b_{i,j}\ .\ $ 则不存在任何一种方案使得 $c$ 能变成 $a.\ $，因为不存在任何一个方案使得 $c_j=a_j$ 成立。

接着我们考虑一种必然能使得 $c=a$ 的情况：

首先，我们把 $c$ 替换成某个 $b_i$ ，此时 $c$ 不存在空位；
然后，我们选择 $b_{i,j}$ 使得 $c_j \ne a_j$ 且
$b_{i,j}=a_j$ ，令 $j$ 为空位，然后操作即可，此时
$c_j$ 必然会变成 $a_j$ 。
重复操作，直到结束。

我们只需要选择 $b_i$ 使得 $b_{i,j}=a_j$ 的数量最大化，把
该 $b_i$ 作为操作的起始即可。

操作数量为 $n + 2 \times (n - cnt)$ ，其中 $cnt$ 是
上述的最大数量。

G

我要熄灯了，代码和 G 题后面补。