【题解】牛客挑战赛41

A 四章

题意:有,把它们分成尽量少的组,使得每组的和不超过

我们使用一个贪心算法,每次先选择尽可能多的,再选择尽可能多的分成一组。可以证明这样能够得到最优解。因为如果在还没被选的数中,把一个换成两个,答案一定不会变劣;所以如果在新选出的一组里存在两个、且存在至少一个没被选,把两个换成一个必然更优。

由于数据范围为,无法直接模拟。

可以先计算出若都足够多,每组要选几个、几个。然后再不断使用这种方案直到之一不够。之后下一组必定会将选完。之后就只剩一种数了,直接计算即可。

复杂度

B 一章

以下图片中红点为割点、红边为桥。

时:

  • ,构造一个三元环即可。
  • ,构造两个点之间连一条边即可。
  • ,无解。因为可以发现若一个桥边的某个端点不是割点,那这个端点必定是度点。

时:

  • 按照以下方法构造:

图片说明

时:

  • 按照以下方法构造:

图片说明

C 欢乐斗地主

设第张牌被替换的时间为,那么地主的操作就等于随机生成了一个排列,而这个排列的答案就是从左到右第一个的位置。

如果我们对于每个,求出有多少个排列满足答案,即可求出原问题的答案。设以上的答案为,那么就等于满足以下条件的排列个数:对于所有的的位置,满足

对于一个,我们可以用以下方法求:从左到右枚举满足,设之前已经有了,那么的选择方案需要满足且和前的选择不同,即答案要乘上。最后,设总共枚举了个数,那么剩下个数的决策还没确定,需要再乘上

容易发现根据以上方法,可以方便地从小到大一次性求出所有。这样我们就在的时间解决了此题。

D 买糖果

一句话题意:求的所有非空子集的和的积。

可以采用meet in middle。先把前一半是空集和后一半是空集的情况用的复杂度处理掉,然后就是前一半和后一半都非空的情况。

设前一半的所有情况的和为,后一半所有情况的和为,那么要求的就是

, 答案就是。那么我们对所有跑个多点求值即可解决这个问题。

复杂度为

E 正整数序列

以下定义

定义为满足以下条件的长为的数组的个数:

  • 对于任意的子序列。
  • 对于最后一个非空序列,满足中不存在数字。特殊地,若,表示没有任何限制。

那么答案就是

对于转移,一共有两种情况:

  • 为空,那么
  • 中第一个数字为,那么为了防止被计算重,间不存在;但是若间为空,间不存在。则依此类推,可得

这样便可以解决这个问题。复杂度

F 时之魔法

我们枚举所有原串或反串中两个后缀,计算它们的贡献,一共有以下几种情况:

  • 属于两个不同的串。那么贡献为乘上所在的串 翻转/没翻转 的概率之积。
  • 属于同一个串,且同为 原串/反串。贡献计算方式与上种情况类似,但概率只需乘一次。
  • 属于同一个串,且一个为原串、另一个为反串。贡献为

对于计算贡献的方式,我们先假定每一对后缀都属于第一种情况。那么总贡献即为每一对后缀的概率之积乘上它们在后缀树上的深度。我们可以利用广义后缀自动机建立后缀树,然后在上面求出答案。

之后我们需要减去属于同一个串的所有后缀的贡献,并重新计算它们的贡献。那么我们可以仅对同一个串的原串与反串建立后缀树,重新计算贡献。而这个过程也可以通过在后缀树上解决。

设字符串总长为、字符集大小为,我们在的复杂的内解决了此题。

全部评论
A题 1 1 10 3   (n+m*2)/k  的写法就不对了
点赞 回复
分享
发布于 2020-06-19 23:34
求教d前半后半均非空的复杂度何为n^2
点赞 回复
分享
发布于 2020-06-21 07:05
淘天集团
校招火热招聘中
官网直投

相关推荐

5 1 评论
分享
牛客网
牛客企业服务