02-02 22:00 山东大学（威海） C++ 发布于山东

关注

题解 | 牛客周赛79题解

小红的合数寻找

https://ac.nowcoder.com/acm/contest/100902/A

声明：出题人没写题解，正好看我内测完有现成的，让我顶上了（

A

只有 $x = 1$ 无解，剩余情况只需输出 $2 \times x$ 即可。

code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300035

B

最大情况的操作方法是红球之间没有白球分隔，最小情况的操作方法是每 $2$ 个红球之间有 $1$ 个白球分隔，两端也尽量有 $1$ 个白球。

容易得到最大的操作数为 $\left \lfloor \frac {n} {2} \right \rfloor$ ，最小的操作数为 $\left \lfloor \frac {n+1} {3} \right \rfloor$

code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300046

C

$ans_1=0,ans_2=1$ 。当 $i \ge 2$ 时，每层会新增 $2^{i-1}$ 个节点，新增的路径有：第 $i-2$ 层 $→$ 第 $i-1$ 层 $→$ 第 $i$ 层共 $2^{i-1}$ 个，和第 $i$ 层 $→$ 第 $i-1$ 层 $→$ 第 $i$ 层共 $2^{i-2}$ 个。共增加 $3 \times 2^{i-2}$ 个路径。题目中 $n$ 较小，可以 $\mathcal O (n \log n)$ 递推求出，也可利用等比数列求和公式 $\mathcal O(\log n)$ 求出。由等比数列求和公式得出 $ans_i = \begin{cases} 0, & i = 1, \\ 3 \times 2^{i-1} - 5, & i > 1. \end {cases}$

code1（递推）：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300022

code2（求和公式）：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300151

D

容易想到的做法是使构造出的数的数位和尽可能小，以免造成麻烦。我们可以构造出含有尽可能多的 $0$ 且数位和 $< 10$ 的数。

设 $n$ 为 $x$ 的数位数。考虑 $x$ 的首位：当首位为 $1$ 时，输出 $2\underbrace{0\dots0}_{n-1个0}$ ；当首位为 $2$ 时，输出 $3\underbrace{0\dots0}_{n-1个0}$ ；当首位为 $3$ 时，输出 $5\underbrace{0\dots0}_{n-1个0}$ ；当首位为 $4$ 或 $5$ 时，输出 $7\underbrace{0\dots0}_{n-1个0}$ ；当首位 $\ge 6$ 时，输出 $11\underbrace{0\dots0}_{n-1个0}$ 。

code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300002

fun fact：本题可以用随机化和高精度通过，最坏时间复杂度我反正是不能预估，但是干过去了（

fun fact code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300203 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300236

E

根据容斥原理， $a_i \times i$ 中满足 $a_i$ 为 $3$ 的倍数且 $i$ 不为 $3$ 的倍数应有 $\frac {n} {2}- \lfloor \frac {n} {3} \rfloor$ 项。从 $a_i$ 为 $3$ 的倍数中选取 $\frac {n} {2}- \lfloor \frac {n} {3} \rfloor$ 个数字的计数为 $C_{\lfloor \frac {n} {3} \rfloor}^{ \frac {n} {2}- \lfloor \frac {n} {3} \rfloor}$ ，从 $i$ 不为 $3$ 的倍数中选取 $\frac {n} {2}- \lfloor \frac {n} {3} \rfloor$ 个数字的计数为 $C_{n -\lfloor \frac {n} {3} \rfloor}^{\frac {n} {2}- \lfloor \frac {n} {3} \rfloor}$ ， $a_i$ 为 $3$ 的倍数和 $a_i$ 不为 $3$ 的倍数分别全排列的计数为 $A_{\lfloor \frac {n} {3} \rfloor}^{\lfloor \frac {n} {3} \rfloor}$ 和 $A_{n -\lfloor \frac {n} {3} \rfloor}^{n -\lfloor \frac {n} {3} \rfloor}$ 。

所以答案为 $C_{\lfloor \frac {n} {3} \rfloor}^{ \frac {n} {2}- \lfloor \frac {n} {3} \rfloor} \times C_{n -\lfloor \frac {n} {3} \rfloor}^{\frac {n} {2}- \lfloor \frac {n} {3} \rfloor} \times A_{\lfloor \frac {n} {3} \rfloor}^{\lfloor \frac {n} {3} \rfloor} \times A_{n -\lfloor \frac {n} {3} \rfloor}^{n -\lfloor \frac {n} {3} \rfloor}$

code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75300054

F

记 $f_n$ 为有 $n$ 个小球时涂色的期望，手推得 $f_0 = 0, f_1 = 0, f_2 = 1$ 。当 $n \geq 3$ 时，可考虑分治：对第一次操作，有等概率的 $n-1$ 个位置可供操作，每个位置可以将左右两边的白球分别划分为 $a,b \left( 0 \leq a,b \leq n-2, a+b=n-2\right)$ 个，这个位置的操作次数期望为 $f_a+f_b+1$ 。所以 $f_n=\frac{\sum_{i=0}^{n-2} (f_i + f_{n-2-i})} {n-1} +1 = 2 \times \frac{ \sum_{i=0}^{n-2} f_i} {n-1} +1$ 。分子的求和项可用前缀和维护。