【题解】牛客小白月赛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最大值，于是转移就变成了：
总复杂度&preview=true)
。
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）
有问题欢迎在评论区交流~
华为工作强度 965人发布
查看12道真题和解析