【题解】牛客小白月赛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号元素，即硅氯，注意到这是个谐音梗，暗示我们找规律，所以找找规律就能发现（大雾）。

令且，可以得到：

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

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

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

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

本题都可以构造出来，不存在输出的情况。

做法不唯一，这里给出一种个人认为简单又好写的构造方式：

（2个y）+（z个c）+（x个y）+（2个c）

经过计算，这样的字符串中yyc子序列的个数是，所以我们先暴力的找一个合适的，再找即可。

此外，注意要特判n=1的情况。总复杂度。