牛客练习赛 73 题解

前言

看到 神仙在群里喊人打比赛就来了，罚时太多了只有 rk3，wxw 永远滴神。

由于是总结里面直接拖过来的，不少写法可能比较简单，题目右边的数字代表相对难度。

例如 8 差不多等于 CF diff 2600~3000 的样子，不得不说这场 diff gap 挺离谱的。

代码可以看提交记录，就不放了，std 其实可读性不太好。

A - 招生：模拟，排序（1）

题意

给定 个人的两个分数 以及满分 ，定义第 个人的分数为 。

若要让小 A 的分数排到第 名，求 的最小值。

，。

题解

计算所有人的分数后排序，答案即为

注意分数不能为负，以及处理实数带来的误差，时间复杂度 。

B - 遥远的回忆：结论（1.5）

题意

给定一个长为 的序列 ，现在有一个长为 的序列 ，用以下方式构造：

1. ，。
2. ，。

求 中最多有多少种不同的数字。

题解

显然一种数字由一对 构成，统计 的连续段数量 ，答案即为 。

时间复杂度 。

C - 生涯回忆录：计数（3.5）

题意

给定一个长为 的序列 ，求所有子区间 和，答案对 取模。

，。

题解

从小到大枚举 ，容易发现 的贡献为两个部分，拆开算即可

其中 为 的出现次数，时间复杂度 。

D - 离别：二位数点（6.5）

题意

给定一个长为 的序列 和参数 ，回答 个询问。

每个询问给定 ，求有多少个 的子区间满足出现次数最多的 的出现次数恰好为 。

。

题解

可以看出在线不可做，考虑离线。用容斥的思想，将 转为 的答案减去 的答案。

对于每一个下标 ，找到一个最小的左端点限制 ，可以用 vector 枚举 递推实现。

对于询问放在右端点上，不难发现是一个二维数点问题，并且发现答案的贡献为

其中 且 最大。不需要用 bit 来维护，双指针扫一遍，然后对于 乘上 的贡献再来一次即可。

时间复杂度 。

E - 羽毛球：概率期望，容斥，组合数学（7.5）

题意

给定两个变量 ，每秒有 的概率 加 、有 的概率 加 。

求至少 秒后， 的概率，答案对 取模。

。

题解

注意是 ，应该 b++​，同时令 方便计算。

忽略 的限制，转换为一个随机游走问题。令 为 的概率，易得

对于不满 的，枚举要得到的 ，组合数计算贡献。若 ，贡献为

否则，贡献为

时间复杂度 。

F - 回音：分块（8.5）

题意

给定一个长度为 的序列 ，和一个长度为 的区间序列 ，回答 个询问。

每个询问给定 ，询问将所有 的 插入可重集 后， 中第 小的数。

。

题解

求出 的 rank，对值域分块，块内维护 rank 的前缀和以及每个询问的出现次数。

对于块内的答案，有 次区间询问区间序列的出现次数。将每个区间差分成两个从 开始的区间，对于询问按照右端点排序，块内区间加单点查询即可。

时间复杂度 。