T1：
两个思路：

• 值域很大，无脑上 map 开个桶，扫一遍即可。
• 值域很大，发现如果题号 $\gt n$ 那么一定做不了，可以忽略。那么只需要开个 $1 \sim n$ 的桶，扫一遍即可。

T2：
发现策略一定是通关前 $i$ 个副本，然后用剩下的次数扫荡已经通关中 $b_j$ 最大的副本 $j$
这容易使用前缀和和前缀 $\max$ 简单计算。

$$ans = \max_j (pre_j + premax_j \times (k - j)) $$

T3：
本场最难题。
首先我们需要知道一个性质，长为 $n$ 的数组，其 $\rm{mex}$ 不会超过 $n$。
那么也就是说，所有 $\gt n$ 的数都可以被忽略，或者被变成 $n + 1$，也不会影响最终结果。
我们发现，答案很小，但是可能的删除情况很多，我们直接枚举删除情况肯定可以，但是显然不可行。所以考虑枚举最终的 $\rm{mex}$ 是多少，然后计算有多少种删除方式。
对于不删除的情况，可以确定初始的 $\rm{mex_0}$
利用 $\rm{mex}$ 的定义我们不难发现，删了数之后 $\rm{mex}$ 只能减少，不能增加，那么我们枚举的量根据性质，就是 $O(n)$ 的了。
考虑一个 $x \lt \rm{mex}_0$ 能够成为答案，有两个条件：

• $x$ 被全部删除
• $\lt x$ 的每个至少保留一个
  根据两个条件，我们可以找到删除数量 $k$ 的一个上下界。
• $k \ge cnt_x$
• $k \le n - x$
  而 $x$ 可以对该区间内的所有 $k$ 做出贡献。
  我们只需要枚举每一个 $x$，找到其贡献的 $k$ 区间，区间 $+1$ 即可。
  问题转化为：
  对于一个数组多次区间加，求这个数组最终长什么样。
  显然可以 $O(n^2)$ 暴力做。利用差分数组，可以做到 $O(n)$。

T4：
输出 $0$ 是个什么抽象操作？？？？？？？

可以考虑一个 DP：

$$f_{i, j} = \begin{cases} f_{i - 1, j} & 与上一个同色 \\ f_{i - 1, j - 1} \times (m - 1) & 与上一个不同色 \end{cases} $$

最初 $f_{1, 0} = m$
那么可以做到 $O(nm)$

问题其实是将一个数组划分为 $k + 1$ 个非空段，染色，要求相邻段颜色不同。
如果我们已经划分好了，那么发现染色步骤对答案的贡献总是乘上 $m \times (m - 1)^k$。
于是只需要考虑划分的方案数即可。
考虑插板法，相当于我们要在 $n - 1$ 个空隙中寻找 $k$ 个空隙作为划分。
那么方案数就是 $\binom {n - 1} k = \frac {(n - 1)!}{k! (n - 1 - k)!}$。
于是答案就是：

$$\binom {n - 1} k \times m \times (m - 1)^k $$

时间复杂度 $O(k)$