竞赛讨论区 > 牛客练习赛 80 官方题解
头像
ceamtic
编辑于 2021-04-10 10:05
+ 关注

牛客练习赛 80 官方题解

A.

先把原串的答案算出来,枚举哪一位反转,判断是不是要减一即可,复杂度 

code

B.

考虑分类讨论:

  1. 当  时,有 ,这部分直接加到  即可;
  2. 当  时,有 ,这部分直接加到  即可;
  3. 当  时,有 ,这部分直接加到  即可;
  4. 否则有 ,有 ,这部分直接加到  即可。

复杂度 

code

C.

考虑先算低于  位的数字有多少。我们把数字看成长为  的序列,然后统计差分序列的数量即可。考虑枚举差分序列之和 ,然后通过插板法,可以得到答案是:

考虑差分,得到最终答案是:

使用 lucas 定理计算组合数即可,复杂度 

code

D.

考虑一个暴力的贪心做法:第一组的左端点一定是 1,直接二分找到最后一个满足题目限制的右端点 ,答案加一;然后把现在左端点设为 ,重复操作......这样是  的。

考虑在确定一个独立的组的时候,使用倍增规约二分。先使用倍增算法,从  开始枚举 ,一次性加入  条边,直到不满足题意。这样可以确定这一组的右端点在某个  内的边内,然后再在这个区间内暴力二分即可。

考虑这样做的复杂度:加边的过程和二分都是  的,也就是说可以花  的时间确定一个大小为  的组,因此总复杂度 

code

E.

考虑先把所有询问离线,然后从小到大枚举询问右端点,用某种数据结构维护每个左端点的答案。

考虑对于一个点,只保留最后一次覆盖它的线段,并把这个点的权值记为线段的标号。

考虑把相邻的权值相同的点合并成同一段来维护,段的权值就是这些点的权值。那么新加入一条线段,就相当于合并(或者说删除)它覆盖到的旧的段,把这些段的权值变成当前枚举到的右端点。

当然可能有一些段会被当前线段从中截断,这种段至多有两个,可以先把它们分解成两段。于是我们可以假定新加入的线段覆盖到的每个段都是完整的。

对应在统计答案的数据结构上,如果合并了一个权值是  的段 ,相当于数据结构上  这个区间的答案整体加上段  的长度,其中  是当前的右端点。由于询问是单点询问,因此可以用树状数组来维护差分数组实现区间修改(或者直接使用线段树),这一部分就是  的。

考虑如何维护出覆盖了哪些线段。可以使用 set 来维护每两个连续段之间的分界点,每次暴力合并连续段即可。根据均摊理论,总复杂度就是 

code

F.

把每个联通块看成一个点,我们会得到一张完全图,而我们要求的是一个生成树。因为  的取值只跟度数序列有关,可以考虑枚举上面这张图的每个点的度数序列 ,然后用这个序列构造生成树的 Prufer 序列,可以得到 Prufer 序列的个数是:

把点的度数分配到原图上,得到方案数是:


加权之后就是:

我们需要对所有可能的  序列求上式的值的和,序列应该满足 ,且所有  之和为 ,且序列长度恰好为 

先把所有  减一,然后考虑对每个  构造生成函数 ,那么答案即是 

这样暴力卷积就是  的了。

考虑优化,设 ,答案变成 。有推导:

根据麦克劳林展开式,我们知道后面的  的  次系数应该是  再乘上原来的系数。形式化的,有等式:

这样就只需要对每个  算出后面的求和的值,直接计算可以做到 ,应该足够通过本题。

考虑构造 ,那么有:


全部评论

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

等你来战

查看全部

热门推荐