牛客小白月赛 73 题解

感谢大家参加牛客小白月赛 73。本场比赛由 氧气少年Kevin 和 罚时大师月色 共同命题。

PDF 题面：点击下载。

A. 最小的数字

本题解法较多：

• 枚举，从 $n,n+1,n+2n,n+1,n+2$ 中，选择较小的、符合条件的输出；
• 直接输出 $\lfloor \frac{x+2}{3}\rfloor \times 3\backslash lfloor\; \backslash frac\{x+2\}\{3\}\backslash rfloor\; \backslash times3$。

B. 优美的GCD

本题限制较松，因此解法较多。

例如：直接输出 $n,2\cdot nn,2\backslash cdot\; n$ 是一种构造方法。

C. 优美的序列

不难发现：如果序列中有两个相同元素，那么一定无解，否则一定有解。

本题解法不止一种，例如：如果有解，排序后输出即可。

D.E. Kevin喜欢零

简单版本思路

维护前缀乘积，使用二分或双指针即可（双指针做法可参考下面的困难版本思路）。

困难版本思路

不难发现：如果 $xx$ 的末尾有 $kk$ 个后导零，那么 $x=p\cdot 10^{k}x=p\backslash cdot\; 10^k$，其中 $pp$ 不能被 $1010$ 整除。

$x=p\cdot 10^k=p\cdot 2^k\cdot 5^{k}x=p\backslash cdot\; 10^k=p\backslash cdot\; 2^k\backslash cdot\; 5^k$。

我们令 $f(x)=f(x)=$ $xx$ 能分解出质因子 $22$ 的数量，例如 $f(8)=3,f(6)=1f(8)=3,f(6)=1$。

我们令 $g(x)=g(x)=$ $xx$ 能分解出质因子 $55$ 的数量，例如 $g(25)=2,g(10)=1g(25)=2,g(10)=1$。

不难发现：$xx$ 的末尾有 $kk$ 个后导零 $\iff \backslash Leftrightarrow$ $\min (f(x),g(x))=k\backslash min(f(x),g(x))=k$。

可以维护 $f(a_i),g(a_i)f(a\_i),g(a\_i)$ 的前缀和，用此性质，$O(1)O(1)$ 计算序列某个子区间乘积的后导零数量。

回到本题，预处理出 $f(a_i),g(a_i)f(a\_i),g(a\_i)$ 的前缀和后，枚举右端点 $rr$，使用两个双指针 $l_1,l_{2}l\_1,l\_2$ 分别维护合法的最小区间边界和合法的最大区间边界。

例如：$n=5,k=3,r=5n=5,k=3,r=5$ 时，有：

$l_{1}l\_1$ 不能再向右移动，因为如果再向右移动，区间乘积后导零个数就小于 $33$； $l_{2}l\_2$ 不能再向左移动，因为如果再向左移动，区间乘积后导零个数就大于 $33$。

对于每个右端点，计算对答案的贡献即可。

F. Kevin的哈希构造

考虑 dp。

令 $f_{i,j,k}f\_\{i,j,k\}$ 表示：当前是第 $ii$ 个字符，目前有 $jj$ 个位置相同，目前的 $hashhash$ 表达式累加到了为 $kk$，这样的状态是否可行。

同时，使用前缀数组 $pr{e}_{i,j,k}pre\_\{i,j,k\}$ 记录每一步选的字符。

转移：

$f_{0,0,0}=\text{true}f\_\{0,0,0\}=\backslash text\{true\}$

$f_{i,j,k}\mathrm{\mid }=f_{i-1,j-[c=S_i],(j-(c{-}^{\mathrm{\prime }}{\text{a}}^{\mathrm{\prime }}+1)\times b^i\mathrm{\%}p+p)\mathrm{\%}p}f\_\{i,j,k\}|=f\_\{i-1,j-[c=S\_i],(j-(c-\text{'}\backslash text\{a\}\text{'}+1)\backslash times\; b^i\backslash \%p+p)\backslash \%p\}$，其中 $cc$ 指当前枚举的 $T_{i}T\_i$ 应放的字符。

最后，如果 $f_{n,k,hash}=\text{false}f\_\{n,k,hash\}=\backslash text\{false\}$，说明无解；否则，由前缀数组逐个输出字符即可。

G. MoonLight 的冒泡排序难题

不难发现，$\text{while}\backslash text\{while\}$ 循环执行次数 $==$ 后面有更小元素的元素数量。换句话说，$\text{while}\backslash text\{while\}$ 循环执行次数 $={\sum }_{i=1}^n[\mathrm{\exists }j>i=\backslash sum\_\{i=1\}^\{n\}[\backslash exists\; j>i$ 满足 。

因此，求 ${\sum }_{i=1}^n[\mathrm{\exists }j>i\backslash sum\_\{i=1\}^\{n\}[\backslash exists\; j>i$ 满足 的期望值即可。

思路1

$\mathsf{h}\mathsf{i}\mathsf{n}\mathsf{t}\mathsf{1}:\backslash sf\; hint1:$ 考虑期望的定义式：$E=\frac{\mathrm{有}\mathrm{效}\mathrm{事}\mathrm{件}\mathrm{数}}{\mathrm{总}\mathrm{事}\mathrm{件}\mathrm{数}}E=\backslash frac\{有效事件数\}\{总事件数\}$。这里，总事件数 $=n!=n!$。

$\mathsf{h}\mathsf{i}\mathsf{n}\mathsf{t}\mathsf{2}:\backslash sf\; hint2:$ 考虑单个元素对有效事件数的贡献。

$\mathsf{h}\mathsf{i}\mathsf{n}\mathsf{t}\mathsf{3}:\backslash sf\; hint3:$ 构造方式:从小到大枚举元素，不断构造新的排列。

我们考虑元素 $ii$ 在长度为 $nn$ 的排列的贡献为：

我们发现元素 $ii$ 的贡献跟前 $i-1i-1$ 元素的位置有关，于是我们先构造 $i-1i-1$ 个元素的排列。

在构造长度为 $ii$ 的排列时，我们可以发现，它是由长度为 $i-1i-1$ 的排列插空得出。

长度为 $i-1i-1$ 的排列有 $ii$ 个空隙，只有前 $i-1i-1$ 个空隙对总事件数有贡献，产生的贡献是 $(i-1)!\cdot (i-1)(i\; -\; 1)!\; \backslash cdot\; (i-1)$ 。

由于排列总长度为 $nn$，剩下 $n-in-i$ 个元素随便放，方案数是 ${\text{A}}_n^{n-i}\backslash text\{A\}\_\{n\}^\{n-i\}$。

于是可以得到，元素 $ii$ 对总事件数的贡献为：$(i-1)!\cdot (i-1)\cdot {\text{A}}_n^{n-i}(i-1)!\backslash cdot\; (i-1)\backslash cdot\; \backslash text\{A\}\_\{n\}^\{n-i\}$。

进一步化简，由 ${\text{A}}_n^{n-i}=\frac{n!}{i!}\backslash text\{A\}\_\{n\}^\{n-i\}=\backslash frac\{n!\}\{i!\}$ 代入得 $n!\cdot \frac{i-1}{i}n!\backslash cdot\backslash frac\{i-1\}\{i\}$。

因此，元素 $ii$ 对总事件数贡献为：$n!\cdot \frac{i-1}{i}n!\backslash cdot\backslash frac\{i-1\}\{i\}$。

因此，我们设 $f_i=f\_i=$ 前 $ii$ 个元素对于长度为 $nn$ 的排列的贡献，那么有：$f_i=f_{i-1}+n!\cdot \frac{i-1}{i}f\_\{i\}=f\_\{i-1\}+n!\backslash cdot\; \backslash frac\{i-1\}\{i\}$。

长度为 $nn$ 的排列的美丽值的期望 $E(n)=\frac{f_n}{n!}E(n)=\backslash frac\{f\_n\}\{n!\}$。

不难发现可以令 $g_i=g_{i-1}+\frac{i-1}{i}g\_i=g\_\{i-1\}+\backslash frac\{i-1\}\{i\}$，此时长度为 $nn$ 的排列的美丽值的期望 $E(n)=g(n)E(n)=g(n)$。

预处理 $g(i)g(i)$，直接回答询问即可。

思路2

假设当前排列长度为 $ii$，美丽值的期望为 $f_{i}f\_i$，

现在随机插入一个新的元素 $i+1i+1$，

这个元素比之前所有的元素都大，

且在 $i+1i+1$ 个可以插入的位置的可能性是均等的，但只有插入的位置不是最后才对美丽值产生贡献。

因此 $f_i=f_{i-1}+\frac{i-1}{i}f\_\{i\}=f\_\{i-1\}+\backslash frac\{i-1\}\{i\}$。

预处理前缀和数组后，直接回答询问即可。