【题解】牛客练习赛73

A:

算出最终得分后排序。

然后算出小A需要的最终得分。

然后算出小A需要的高考分。

记得特判0的情况。

[std](https://www.luogu.com.cn/paste/i7t03z3v)

B:
如果一个值相同段用最后一个算贡献,那么连续的1 0答案+1,以及最后一位特判一下。

[std](https://www.luogu.com.cn/paste/rw21jmh7)


C:
从1~n枚举遗憾值为1~n。

设i出现了$c_i$次。

那么这个遗憾值x的生涯回忆录种类就是:$\prod_{i  < x}(2^{c_i}-1) * \prod_{i  > x}(2^{c_i})$。

用前后缀和维护一下就可以O(n)计算所有数的贡献了。

[std](https://www.luogu.com.cn/paste/famdhxwz)

D:

对于每个下标$i$,求出它的一个范围$[x,y]$使得区间$[i,j](x \le j \le y)$中出现最多的数正好出现$k$次。

然后l,r的询问就相当于一个二维数点的问题。

那么树状数组维护一下即可。

O(nlogn)

[std](https://www.luogu.com.cn/paste/b2tqgf7t)

E:

如果已经达到了$a$分,那么相当于就是一个链上随机游走的问题了。

设f[i]表示分差为i的时候的获胜概率,那么$f[i] = (1-p)*f[i-1] + p*f[i+1]$

然后解一下这个方程即可。

对于分不到$a$的,考虑计算出当有人分到达$a$时,分差是$x$的概率。

这个用组合数算一下,具体见代码。

O(nlogn)

[std](https://www.luogu.com.cn/paste/p5jrmelx)

F:

值域分块。

首先确定每个询问的答案在哪个块的范围内,几次前缀和维护一下每个询问里在每个块的范围内出现了多少个数。

然后对于块内的答案,相当于$n \sqrt n$次询问被多少个[L,R]内的区间$[x_i,y_i]$包含。这个拆成$[1,L-1]$的和$[1,R]$的然后减一下。

按照右端点排序,然后就转换成$O(n)$次区间加,$O(n \sqrt n)$次单点询问,这个分块维护即可达到总复杂度$O(n \sqrt n)$。

[std](https://www.luogu.com.cn/paste/qdkk2ui6)
全部评论
orz Ynoi😍
1 回复
分享
发布于 2020-11-22 22:14
这个 E 的样例真阴间
1 回复
分享
发布于 2020-11-22 22:19
阿里巴巴
校招火热招聘中
官网直投
orz
点赞 回复
分享
发布于 2020-11-22 22:16
orz Ynoi😍
点赞 回复
分享
发布于 2020-11-23 07:47
orz Ynoi😍
点赞 回复
分享
发布于 2020-11-23 11:56
orz %%%
点赞 回复
分享
发布于 2020-11-23 16:33
请问大佬E题:f[i]=p*f[i+1]+(1-p)*f[i-1]是什么意思,不应该是i可以从i+1输一场*(1-p),和从i-1赢一次*p过来的,所以是f[i]=(1-p)*f[i+1]+p*f[i-1]吗
点赞 回复
分享
发布于 2020-11-23 16:33
这场D告诉我离线真憨,这场F又告诉我,我就是个憨憨
点赞 回复
分享
发布于 2020-11-25 17:16

相关推荐

点赞 评论 收藏
转发
3 收藏 评论
分享
牛客网
牛客企业服务