【题解】牛客小白月赛38题解

预计难度:
签到:A<B
简单:D<C
中等:F<G<E
中难:H<I
难:J

实际难度:
签到:A<B
简单:D
中等:C<G
中难:F<E<H<I
难:J

总体还算预期内,主要是低估了CEF三题的难度,所以成为了在CF里会被形容为有很大gap的一套题,三题到四题、四题到五题都稍微有一道坎儿,坏。

A题

阅读理解+字符串处理题,按题意模拟即可。

B题

按照素数、合数、1来对数字分类的话,输出是YES当且仅当两个数中一个是素数一个是1。因此,我们使用的算法来判断两个数是不是素数即可。

C题

表示第个数结尾的最长合法行棋子序列,有:

所以我们在dp的同时维护数组表示颜色为打劫位置为的dp最大值,于是转移就变成了:

总复杂度

D题

输出即可,原因如下:

因为本题的名字叫Mendeleev 1417,暗示门捷列夫的元素周期表当中的14和17号元素,即硅氯,注意到这是个谐音梗,暗示我们找规律,所以找找规律就能发现(大雾)。


正经的原因:
由二项式定理


,可以得到:

进行移项,可以看出,从个数中选奇数个数的方案等于从中选偶数个数的方案。

由于本题不允许不选,所以两者之间会差一,所以输出

E题:
注意到如果输入数字串没有的话,那么我们暴力枚举区间(例如枚举区间左端点,让右端点逐渐增加),在当前区间积已经超过时立刻break(因为区间长最大就),那么这样break来做复杂度就是的了,

那么有咋办呢,我们只要预处理出表示下一个非一数字的位置,让右端点逐渐增加时不是加一而是沿着走一步即可。于是同上,总复杂度

F题:

直接计算弦长期望比较困难(可能并不困难,但对本已经不会微积分的老狗比较困难),考虑转为计算每条弦中点(即题面中的点P)到圆心的距离的期望。
方法二的该期望长度显然是0.5
方法一的期望长度可以积分计算:

所以,我们可以根据输入数据来计算出输入数据中OP的平均长度,看和以上两个值那个比较接近,来判断来自于哪种方法。
也可以真的去计算下弦长的期望来判断;还可以自己也生成一下两种数据,看哪个和输入相似度比较大(当然这需要合理的定义相似度)。

G题:


本题都可以构造出来,不存在输出的情况。
做法不唯一,这里给出一种个人认为简单又好写的构造方式:
(2个y)+(z个c)+(x个y)+(2个c)
经过计算,这样的字符串中yyc子序列的个数是,所以我们先暴力的找一个合适的,再找即可。
此外,注意要特判n=1的情况。总复杂度

(HIJ公式好多,懒得手敲了,这里直接放图了,点击看大图更清晰.jpg)





有问题欢迎在评论区交流~
全部评论
zywdltql
点赞 回复
分享
发布于 2021-09-18 22:16
zywtql
点赞 回复
分享
发布于 2021-09-18 22:17
阿里巴巴
校招火热招聘中
官网直投
不懂就问,E 题暴力为什么不行呢,1 ~ 1e5,只有 [2...9] 因子的只有 700 左右(纯提问,WA 了) https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48782024
点赞 回复
分享
发布于 2021-09-19 06:59
c主要没看懂题意。。。
点赞 回复
分享
发布于 2021-09-22 16:55
g题的子序列个数公式是咋推出来的🤕🤕
点赞 回复
分享
发布于 2021-09-22 21:02
F题 第一种方法的期望公式是不是错了   应该是
点赞 回复
分享
发布于 2021-09-24 16:16

相关推荐

11 4 评论
分享
牛客网
牛客企业服务