牛客练习赛 114 题解

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

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

A. 光速签到

标签

模拟

思路

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

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

标签

概率期望

思路

若 则无解，否则输出 即可。

C. Kevin的七彩旗

标签

dp、暴力

思路

考虑 dp。

考虑处理序列 的连通块，假设某段连通块为 ，则该连通块应该满足：

• 。
• 若 ，则必须满足 。
• 若 ，则必须满足 。
• 若 ，则必须满足 。

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

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

仅当 是某个连通块的右端点时， 才有意义。

转移有：

答案 。

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

时间复杂度 。

D. 长途的春天

标签

贪心

思路

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

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

按顺序进行判断是否合法即可。

E. Kevin的抽奖黑幕

标签

dp、概率期望

思路

不难发现，对于参与抽奖的每个人可以单独计算贡献。

考虑 dp。

用 表示当前是第 轮，此人连续 轮没有获奖，此状态到 轮抽奖结束，获得奖品数量的期望。

转移有：

答案 。

PS：这里 的做法可以通过本题，但不难发现，上面的转移方程经过归纳整理，可以进一步降低复杂度，感兴趣的读者可以进一步思考。

F. Kevin去砍树

标签

双指针、二分

思路

不难发现，被砍伐的树的高度有下面的特点：

• 呈现单调或单峰的形态；
• 没有重复的高度。

上面的两条性质，在区间上都有着随右端点右移，左端点单调的特点。

对于每个位置 ，使用双指针预处理出它能取到的最左边的 ，满足 无重复元素，记 。

预处理出对于每个位置 ，预处理出它能取到的最左边的 ，满足 ，可以用 dp 或者二分实现，记 。

预处理序列 的前缀和，对于每个位置 ，求出 ，答案取最大值即可。

G. 图上异或难题

标签

线性基

思路

注意异或的性质。

对于图上一个点 而言，如果与 有连边的 的颜色和 不同，那么可以将这条边的边权的贡献算入答案。

考虑将边的贡献转化为点的贡献。

设与第 个点相连的所有边的边权异或为 ，所有 组成的集合为 ，那么答案为 。

使用线性基维护即可。