竞赛讨论区 > 【题解】牛客练习赛73
头像
Ynoi
编辑于 2020-11-23 10:25
+ 关注

【题解】牛客练习赛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)

全部评论

(8) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐