牛客练习赛 73 题解
前言
看到 神仙在群里喊人打比赛就来了,罚时太多了只有 rk3,wxw 永远滴神。
由于是总结里面直接拖过来的,不少写法可能比较简单,题目右边的数字代表相对难度。
例如 8 差不多等于 CF diff 2600~3000 的样子,不得不说这场 diff gap 挺离谱的。
代码可以看提交记录,就不放了,std 其实可读性不太好。
A - 招生:模拟,排序(1)
题意
给定 个人的两个分数 以及满分 ,定义第 个人的分数为 。
若要让小 A 的分数排到第 名,求 的最小值。
,。
题解
计算所有人的分数后排序,答案即为
注意分数不能为负,以及处理实数带来的误差,时间复杂度 。
B - 遥远的回忆:结论(1.5)
题意
给定一个长为 的序列 ,现在有一个长为 的序列 ,用以下方式构造:
- ,。
- ,。
求 中最多有多少种不同的数字。
题解
显然一种数字由一对 构成,统计 的连续段数量 ,答案即为 。
时间复杂度 。
C - 生涯回忆录:计数(3.5)
题意
给定一个长为 的序列 ,求所有子区间 和,答案对 取模。
,。
题解
从小到大枚举 ,容易发现 的贡献为两个部分,拆开算即可
其中 为 的出现次数,时间复杂度 。
D - 离别:二位数点(6.5)
题意
给定一个长为 的序列 和参数 ,回答 个询问。
每个询问给定 ,求有多少个 的子区间满足出现次数最多的 的出现次数恰好为 。
。
题解
可以看出在线不可做,考虑离线。用容斥的思想,将 转为 的答案减去 的答案。
对于每一个下标 ,找到一个最小的左端点限制 ,可以用 vector
枚举 递推实现。
对于询问放在右端点上,不难发现是一个二维数点问题,并且发现答案的贡献为
其中 且 最大。不需要用 bit 来维护,双指针扫一遍,然后对于 乘上 的贡献再来一次即可。
时间复杂度 。
E - 羽毛球:概率期望,容斥,组合数学(7.5)
题意
给定两个变量 ,每秒有 的概率 加 、有 的概率 加 。
求至少 秒后, 的概率,答案对 取模。
。
题解
注意是 ,应该 b++
,同时令 方便计算。
忽略 的限制,转换为一个随机游走问题。令 为 的概率,易得
对于不满 的,枚举要得到的 ,组合数计算贡献。若 ,贡献为
否则,贡献为
时间复杂度 。
F - 回音:分块(8.5)
题意
给定一个长度为 的序列 ,和一个长度为 的区间序列 ,回答 个询问。
每个询问给定 ,询问将所有 的 插入可重集 后, 中第 小的数。
。
题解
求出 的 rank,对值域分块,块内维护 rank 的前缀和以及每个询问的出现次数。
对于块内的答案,有 次区间询问区间序列的出现次数。将每个区间差分成两个从 开始的区间,对于询问按照右端点排序,块内区间加单点查询即可。
时间复杂度 。