Bazoka13

编辑于 2021-05-09 22:54

+ 关注

题解-牛客练习赛82 精

Huge thanks to those who helped make this round possible:

对于题目解决方法和顺序给出意见的验题人。
参与内测并给予反馈的验题人和学弟。
清楚姐姐等工作人员出色的帮助。
Nowcoder 平台。

由于经验不足，对于题面描述不够清楚的问题深表歉意。

A

设一个位置 $i$ ( $1 \le i \le n - 4$ ) 是匹配的当且仅当 $S[i,i+4]=\text{mocha}$ ，可以在 $O(n)$ 的时间内求出所有的匹配位置。

考虑将所有匹配的位置排序后得到序列 $a_1,a_2,\cdots,a_m$ ，如果 $m < k$ 则无解，否则答案即为 $\min \limits _{i=1}^{m-k+1}\left(a_{i+k-1}-a_i+5\right)$ ，同样可以在 $O(n)$ 的时间内求出。

B

注意到 $\dfrac{\prod \limits _{i=l} ^ r i}{(r-l+1)!}=\dfrac{r!}{(l-1)!(r-l+1)!}=\dbinom{r}{l-1}$ ，从而 $\dfrac{\prod \limits _{i=l} ^ r i}{(r-l+1)!} \bmod (r-l+1)! = 0$ 。

无论进行多少次操作 1 或操作 2， $a_i$ 始终是 $i$ 的倍数，因此恒有 $\dfrac{\prod \limits _{i=l} ^ r a_i}{(r-l+1)!} \bmod (r-l+1)! = 0$ ，对于所有操作 3 直接输出 $0$ 即可。

C

首先，对于相同的 $b_i$ ，对应的 $c_i$ 必然相同，否则无解。

接下来，处理出每个数所在位置的最小值 $f_i = \max\{c_j \mid \langle b_j,i \rangle \in A\}$ 。

从 $1$ 到 $n$ 遍历每个位置 $i$ ，同时维护一个小根堆保存当前可以放但是还没放的数：

如果不存在 $c_j=i$ ，那么直接从小根堆中拿出最小的数放在该位置即可。
否则，放置的数 $x$ 必须满足 $\forall c_j =i,\langle b_j,x \rangle \in A$ ，容易发现这样的数必然有 $f_x=i$ 。因此考虑集合 $\{x \mid f_x = i,\forall c_j =i,\langle b_j,x \rangle \in A\}$ ，如果该集合为空，说明无解；否则将该集合中最小的数放到该位置上，其它数全部加入小根堆。

这种情况的选择只涉及 $f_x=i$ 的 $x$ ，与之前的选择完全独立，因此不会影响贪心的正确性。

时间复杂度为 $O(n \log n + m)$ 。

D

如果 $n=1$ ，答案即为 $\dfrac{q}{p}$ ，如果 $\dfrac{p}{q}=1$ ，答案即为 $F_1=1$ 。

下面考虑 $0.7 \le \dfrac{p}{q} < 1 , n > 1$ 的情况。可以证明每次将未被发送的 $k$ 个数据包全部发送是最优策略。

设 $f_i$ 是最优策略下发送 $i$ 个数据包的期望代价， $f_0=0$ ，当 $i > 0$ 时恒 $f_i \ge f_{i+1}$ ，下面使用数学归纳法证明：

当 $i=1$ 时，显然有 $f_1=\dfrac{F_nq}{p}$ 。对于 $2$ 个数据包，考虑每次把未被发送的数据包全部发送，设这样做的代价为 $g$ ，则有如下等式：
$g={\left(1-\dfrac{p}{q}\right)}^2g+\dfrac{2p}{q}\left(1-\dfrac{p}{q}\right)\dfrac{F_nq}{p}+F_{n-1}$
得到 $g=\dfrac{2F_n\left(1-\dfrac{p}{q}\right)+F_{n-1}}{1-{\left(1-\dfrac{p}{q}\right)}^2}$ ， $g-f_1=\dfrac{F_{n-1}-\dfrac{pF_n}{q}}{\dfrac{2p}{q}\left(1-\dfrac{p}{q}\right)}$ ，分母恒为正，当 $n>1$ 时 $\dfrac{F_{n-1}}{F_n} < 0.7$ 因此分子恒为负，从而 $f_2 \le g < f_1$ 。
当 $i > 1$ 时，假设当 $j < i$ 有 $f_{j} \ge f_{j+1}$ 恒成立。考虑对于前 $i-1$ 个数据包按照 $i-1$ 个数据包的最优策略选择是否发送，同时选择发送最后一个数据包，显然这一次发送的花费相比 $i-1$ 个数据包的最优策略的一次发送花费更少。同时，每一种前 $i-1$ 个数据包的发送情况都可以等概率地对应 $i-1$ 个数据包对应策略中的一种情况，且因为最后一个数据包有可能发送失败，所以剩余数据包数量不减，根据归纳假设发送剩下数据包的期望代价不会增加，从而 $f_i \ge f_{i+1}$ 。

另一方面，类似上述过程，对于 $i$ 个数据包的最优发送策略即为在 $i-1$ 个数据包最优发送策略的基础上添加发送最后一个数据包，从而每次将未被发送的 $k$ 个数据包全部发送即为最优策略。

因此有如下递推式：

$f_i = F_{n-i+1}+\sum \limits _{j=0}^i \dbinom{i}{j}{\left(\dfrac{p}{q}\right)}^j{\left(1-\dfrac{p}{q}\right)}^{i-j}f_{i-j}$

将右侧 $f_i$ 的系数移项后即可 $O(n^2)$ 求解。

E

假设有恰好 $2i$ 对手套被执行第二种操作，一人分走一双，那么这 $2i$ 双手套的选择有 $\dbinom{n}{2i}$ 种方案，将这 $2i$ 双手套分给两个人又有 $\dbinom{2i}{i}$ 种方案，而剩下 $n-2i$ 双手套被执行第一种操作，一人分走一只，方案唯一。因此总方案数即为：

$\sum \limits _{i=0} ^ {\lfloor \frac{n}{2} \rfloor} \dbinom{n}{2i}\dbinom{2i}{i} = \sum \limits _{i=0} ^ {\lfloor \frac{n}{2} \rfloor} \dfrac{n!}{(n-2i)!i!i!}$

给出的 $p$ 不是质数，一些数的逆元可能不存在。设 $p=\prod \limits _{i=1}^m p_i^{k_i}$ ，其中 $p_i$ 均为质数，可以求出方案数对每个 $p_i^{k_i}$ 取模的结果再使用中国剩余定理进行合并。

下面以求解方案数对 $p^k$ 取模为例，其中 $p$ 是质数。

对于正整数 $i=p^xq$ ，其中 $\gcd(p,q)=1$ ，令 $f_{p,i}=q$ ， $g_{p,i}=x$ 。

设 $F_{p,k,i}=\left(\prod \limits _{j=1} ^i f_{p,j}\right) \bmod p^k$ ， $F_{p,k,i}^{-1}$ 为 $F_{p,k,i}$ 在 $p^k$ 意义下的逆元， $G_{p,i}=\sum \limits _{j=1} ^i g_{p,j}$ 。

试除 $1,2,\cdots,n$ 每个数中的质因子 $p$ 就可以得到 $f_{p,i}$ 和 $g_{p,i}$ ，总试除次数不超过 $\sum \limits _{i=1} ^{\infty} \dfrac{n}{p^i} \le n$ 。

通过前缀积和前缀和即可得到 $F_{p,k,i}$ 和 $G_{p,i}$ ，使用一次扩欧求逆元可以得到 $F_{p,k,n}^{-1}$ ，再倒着进行递推即可得到其余的 $F_{p,k,i}^{-1}$ 。

方案数对 $p^k$ 取模的结果即为：

$\left(\sum \limits _{i=0} ^ {\lfloor \frac{n}{2} \rfloor} F_{p,k,n}F_{p,k,n-2i}^{-1}F_{p,k,i}^{-1}F_{p,k,i}^{-1}p^{G_{p,n}-G_{p,n-2i}-2G_{p,i}}\right) \bmod {p^k}$

对于每个 $p^k$ ，上述过程时间复杂度为 $O(n + \log p^k)$ 。

设 $\pi(p)$ 为 $p$ 的不同质因子的个数，中国剩余定理合并中还需进行 $\pi(p)$ 次求逆元，因此总时间复杂度不超过 $O((n+\log p)\pi(p))$ ， $p \le 10^7$ 时 $\pi(p) \le 8$ ，足够通过本题。

F

切痕存在两种情况：

一端在端点上

对于这种情况，我们可以利用双指针遍历多边形上的端点，同时维护两个双指针及其之间的点组成多边形的面积，如果当前维护的多边形面积超过了总面积的一半，我们就可以确定出另一端所在的边，之后我们可以计算出超出的面积，利用叉积等操作计算出另一端在边上的位置，从而更新答案。

两端都不在端点上

这种情况同样可以使用双指针计算，只不过遍历的对象变成了多边形的边，如何找到合法边对在此不再赘述，仅阐述如何处理合法边对计算答案。

如图，延长 $AB$ 交 $DC$ 延长线于 $F$ 。设 $GF=a$ ， $HF=b$ ， $GH=c$ ， $∠F=θ$ 。
图片说明

我们有 $c^{2}=a^{2}+b^{2}-2abcos\theta$ ，而注意到 $S_{GFH}=S_{GBCH}+S_{FBC}$ ，又有 $S_{GFH}=\frac{1}{2}absin\theta$ ，因此 $ab$ 是定值。由基本不等式，我们很容易知道， $a=b$ 时， $c$ 取极小值；并且 $c$ 没有极大值。