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$ 。
转换一下：
&\sum_{i = 2}^{N} \sum_{j = 1}^{i – 1} (A_i – A_j)^2 \\
=&\sum_{i = 2}^{N} \sum_{j = 1}^{i – 1} (A_i^2 + A_j^2 – 2A_iA_j) \\
=&(n-1)\sum_{i=1}^nA_i^2 + \sum_{i>j}2A_iA_j \\
=&(n-1)\sum_{i=1}^nA_i^2 + \sum_{i=1}^nA_i\sum_{j=1}^nA_j
\end{aligned}
$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$ 种不同数字的数量，然后分两类讨论：
- 前 $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} - 前 $i-1$ 位恰好等于 $S$ 的前 $i-1$ 位：
这种情况下，第 $i$ 位只能选择严格小于 $S_i$ 的数才能保证前 $i$ 位严格小于 $S$ 。
最终不要忘记特判一下 $S$ 本身是不是答案就好了。
test
Hello world!