牛客练习赛 114 题解

感谢大家参与牛客练习赛 114 ！

出题人：氧气少年Kevin（CF;牛客）；罚时大师月色（CF;牛客）；长途（CF;牛客）
题面 PDF：点击下载

A. 光速签到

思路

将序列降序排序后，如果末尾数字是否为 $0$ 则无解，否则输出排序后的序列即可。

B. 相信我,这真的是一个暴力!

思路

若 $\frac{a_1}{10}\cdot \frac{b_1}{10} \frac{a_2}{10}\cdot \frac{b_2}{10} \frac{a_3}{10}\cdot \frac{b_3}{10}=1$ 则无解，否则输出 $\frac{1}{1-(\frac{a_1}{10}\cdot \frac{b_1}{10} \frac{a_2}{10}\cdot \frac{b_2}{10} \frac{a_3}{10}\cdot \frac{b_3}{10})}$ 即可。

C. Kevin的七彩旗

思路

考虑 dp。

考虑处理序列 $a$ 的连通块，假设某段连通块为 $a_l\dots a_r$ ，则该连通块应该满足：

$\lbrace a_l\dots a_r \rbrace\in[1,m]$ 。
若 $r-l 1>1$ ，则必须满足 $a_i=a_{i-1} 1,l<i\leq r$ 。
若 $l>1$ ，则必须满足 $a_{l-1}\neq a_l-1$ 。
若 $r<n$ ，则必须满足 $a_{r 1}\neq a_r 1$ 。

不难发现，每个元素最多属于 $1$ 个连通块，部分元素可能不属于任何连通块。

令 $f(i)$ 为拼成美丽序列前 $i$ 项，最少需要选出的互不相交的子段的数量。

仅当 $i$ 是某个连通块的右端点时， $f(i)$ 才有意义。

转移有：

alt

答案 $=f(n)$ 。

其中， $len_i$ 是在所有以数字 $i$ 结尾的连通块中，最长的连通块的长度。

时间复杂度 $O(n)$ 。

D. 长途的春天

思路

考虑对原牌堆进行排序，计算每个牌号 $i$ 的数量 $cnt_i$ ，从小到大去贪心的组成顺子，策略如下：我们每次遍历时，我们要维护以牌号 $i$ 为结尾的顺子长度，为了能凑出来顺子，我们每张牌号 $i$ 前面都会接一个顺子。

如果牌号 $i$ 的数量大于等于牌号 $i-1$ 的数量，那么每张牌号 $i$ 的牌都可以接上前面所维护的顺子，如果多出来就自己作为顺子的开头。
如果牌号 $i$ 的数量小于牌号 $i-1$ 的数量，应当优先选择长度较短的顺子，然后接上这个顺子，那么多出来的 $i-1$ 前缀应当判断是否合法(组成顺子)。