ABC194 题解

[toc]

AC 代码

A – I Scream

B – Job Assignment

C – Squared Error

给定一个大小为 $N$ 的数列 $A$ ，求 $\sum_{i = 2}^{N} \sum_{j = 1}^{i – 1} (A_i – A_j)^2$ 。

$N\leq 3\times 10^5$ 。

转换一下：

$O (N)$ 计算即可。

D – Journey

有一个 $N$ 个点的图，Takahashi 初始站在点 1，他每次都有 $\frac {1}{N}$ 的概率跳到任意一个点，询问他遍历图上所有点的期望跳跃次数。

$N\leq 10^5$ 。

假设当前 Takahashi 已经遍历了 $i$ 个点，那么他下一次跳跃能够到达一个未曾遍历过的点的概率为 $\frac {N-i}{N}$ ，换算成期望就是 $\frac {N}{N-i}$ 轮，由于每一次的选择独立，累加即为期望。

E – Mex Min

给定一个大小为 $N$ 的数列 $A$ ，询问数列 $A$ 中所有长度为 $M$ 的连续区间中 $MEX$ 的最小值。

$M<N\leq 1.5\times 10^6, 0\leq A_i<N$ 。

考虑到我们扫过的区间一定是 $[1,M], [2,M+1],\ldots$ 这样的连续区间，因此每次换到下一个区间都相当于新加入一个数，然后再去掉一个数，可以直接用树状数组更新。查询 $MEX$ 则考虑树状数组上倍增，求前 $K$ 个数的和是否等于 $K$ ，时间复杂度 $O (N\log N)$ 。

F – Digits Paradise in Hexadecimal

给定一个长度为 $N$ 的十六进制数字 $S$ ，询问 $[1,N]$ 的十六进制整数中有多少个数含有 $K$ 种不同数字。

$N\leq 2\times 10^5,K\leq 16$ 。

设 $dp [i][j]$ 表示前 $i$ 个数位严格小于 $S$ 的前 $i$ 位并且含有 $j$ 种不同数字的数量，然后分两类讨论：

1. 前 $i-1$ 位已经严格小于 $S$ 的前 $i-1$ 位：

   这种情况下，第 $i$ 位可以随便选择，因此有两种不同转移：

   $$\begin{cases} dp[i][j]=dp[i][j]+dp[i-1][j-1]\times (16-j)\\ dp[i][j]=dp[i][j]+dp[i-1][j]\times j\\ \end{cases}$$
2. 前 $i-1$ 位恰好等于 $S$ 的前 $i-1$ 位：

   这种情况下，第 $i$ 位只能选择严格小于 $S_i$ 的数才能保证前 $i$ 位严格小于 $S$ 。

最终不要忘记特判一下 $S$ 本身是不是答案就好了。