02-02 21:59 已编辑山东大学（威海） C++ 发布于山东

关注

题解 | 牛客周赛79题解

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

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$ 。分子的求和项可用前缀和维护。

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

全部评论

推荐最新楼层

_轨迹_

北京邮电大学算法工程师

F题，按照操作数分类，选k个时，对分子贡献为C(k+1,n-2k)*k!*k，对分母贡献为C(k+1,n-2k)*k!，这样算出来为什么只能得四十分呀？（我还有个疑问，计算时可不可以对分母先取余再取逆元）

点赞回复分享

发布于 02-02 21:15 河北

05-31 19:11

已编辑

网易互娱_前端开发(准入职员工)

美团前端面经合集

核心本地 - 美团平台- 前端面经一、技术面问题开发效率与工程实践AI 提升开发效率的具体场景懒加载和条件渲染策略优化的背景是否使用过 React、对 React 和 Vue3 的看法与对比对 Node.js 的了解Webpack 使用经验为什么使用状态管理（解决什么问题）使用过 EventBus 吗？和 Pinia 的区别JavaScript 基础JS 数组方法手写题：数组扁平化（要求使用 reduce 方法）输出题：事件循环机制二、反问环节地图相关业务技术栈是否偏移动端（如 React Native）关注能力：基础、学习能力、沟通能力美团前端二面事件循环被问到事件循环的概念和执行机制，结合...

想实习转正，又想准备秋招，我该怎么办美团求职进展汇总

点赞评论收藏

不愿透露姓名的神秘牛友

05-29 22:21

社招Offer选择：小马智行、追觅科技

Offer1：小马智行,深圳,测试开发工程师,17.0k*16.0,Offer2：追觅科技,深圳,嵌入式工程师,18.0k*15.0,

嵌软狗都不学：各位base深圳的同事，作为也是并肩作战的一员，今天想站在管理视角，和大家开诚布公地聊一聊:从近几个月的上下班数据对比看来，我们发现一个明显的差异:深圳同事的在岗时间普遍比苏州同事短。很多深圳同事早上9点之后才到公司，晚上不到 20 点就下班了;而总部那边，20点半甚至 22 点后还有不少同事在办公室忙碌，特别是研发团队，加班更是常态。相信去过苏州的同事，对这种场景都不陌生。我很好奇，这是因为苏州工作任务太重还是咱们深圳同事效率真的高到能在更短时间内完成工作?MOVA在深圳成立分公司是为了吸引更优秀的人才贡献更多更高质的价值，公司管理层给我反馈的是深圳招到的多是行业的专家大拿，大部分都是薪资比苏州高的，而且我们办公的租金等也远高于苏州的..MOVA虽脱胎于强壮的集团母体不久，各业务板块尚未实现全面盈利，虽说公司管理层目光长远，不纠结当下的人才投入，但行业内的普遍标准是，员工创造的价值要达到公司雇佣成本的 15 倍以上。大家不妨自我审视一下，自己是否达到了这个标准?如果是抱着划水、按时打卡走人拿毛爷爷的心态那不适合来MOVA，那样过下去不但自己过得尴尬也会影响MOVA这个大船的攻城略地的速度.我并非鼓励大家盲目加班，而是倡导高效工作，拒绝无效忙碌，不要让项目进度因低效受影响，也别把精力浪费在和苏州同事拼打卡时长上，提倡更高的人效比;考虑到两地地域和交通差异，相信大家会找最适合自己发挥的工作方式(比如按时下班后1小时到家晚饭后继续未竟工作等..)大家在遵守公司规章的情况下尽情地体现自己的能力价值，为MOV!和深圳公司争光我们在这边才能更安心更有信心的工作下去;请客BU长、名部门长、项目管理和各业务单元负责人，全面梳理团队情况，及时评估成员工作负荷与成果质量，坚决清退划水害虫痕疫，践行公司价值观，相互监督，防止管理漏洞及渎职。感谢人家的理解，也请人家多担待我的直言不讳……

点赞评论收藏