【题解】牛客挑战赛45

比赛中途因为一些问题更正了题面,再次为带来的麻烦道歉。非常抱歉。

然后 C 题的赛时问题可以查看 C 的题解了解,实在是非常抱歉。不好意思。

B - solution

对于树,当前点为根的子树内点权和不为 的倍数时选择当前点连向其父亲的边,否则不选择这条边。

C - solution

枚举操作的区间的长度,对应求出 的最大值,然后从高位向低位贪心求代价。

复杂度

  • 非常抱歉这道题糟糕的题面为您带来了糟糕的比赛体验,数据的问题在于出题人的题面写的读入规则是 ,但实际上出题人的代码读入顺序为 ,也就是说我们的题面写反了/lb
  • 但是小样例满足无论 读反答案都是一样的,所以我们误以为是选手提交有问题。实在是抱歉。
  • 然后本次比赛的题面存在许多细节都存在描述不严谨以及错误等问题,非常抱歉为您带来了如此糟糕的比赛体验,也与我们在比赛前没有对题目进行仔细的检查有关。

D - solution

由于 以及每次修改是随机生成的,所以我们每次修改之后暴力遍历整个子树修改对应点的深度的期望次数是 (注意到单次复杂度的期望为

我们考虑对于 上的每个点下面再挂一个点,边权为在 中的深度。此时两点的距离即为两个节点新挂的节点的距离。由于边权非负,所以我们等价于维护新树上的直径。

每次修改操作,我们可以将 子树中的每个点依次修改(即暴力)然后动态维护直径即可,标算在实现上采取的是 的 LCA,所以复杂度为 ,但范围只开了 ,所以 的做法也可以通过本题。

  • 动态维护直径:
  1. 如果当前修改的这个点是修改前树的直径上的一个端点,那么另一个端点一定是新的直径上的一个端点,比较一下即可。
  2. 如果当前修改的点不是修改前树的直径的一个端点,那么原来树的直径上的端点至少有一个是新的树的直径的端点,也比较一下即可。

E - solution

先考虑 的情况,令 表示节点 的度数。

删除一个点,对于联通块数量的影响为:,然后与他相连的点的度数都 。也就是如果一条边连接的两个点同时被选择,就有 的贡献。

每个点被选中的概率均为 ,所以点权的期望贡献即 。再考虑边,一条边的两个端点被同时选中的概率为 ,所以边的贡献为:

所以对于一棵树,答案为:

对于仙人掌,所以如果一个点的度数为 ,且其处于环上,那么删除其对于联通块数量的影响为:;否则为:,并且这个环会被破坏掉

发现每个环也只有第一次被选中的时候有影响,且彼此对于答案的贡献的期望也是独立的!

不考虑环的贡献的计算方式显然和树的计算方式一样。对于一个大小为 的环被选中的概率为:。由于环的贡献是负数,所以我们只需要最大化: 即可。

注意到,环的数量固定是 的,对于大小 的环对于答案的贡献显然没有大小为 的环对于答案的贡献优。同时,如果我们能够构造一个大小 的环,那么就一定可以构造一个大小为 的环然后挂一条链。

所以我们构造的方案一定是由很多个大小为 的环构成的仙人掌图,一种可行的方案是形如:
graph.png

于是最后的答案其实就是:

把组合数拆开化简一下就可以得到:

F - solution

定义 表示对于图 其最小生成树的最大边权小于等于 的情况下的 MST 的边权和的期望。

定义 表示对于图 其最小生成树的最大边权小于等于 的情况下其 MST 的边权和的平方的期望。

可以明确的一点为, 均为关于 的多项式,于是只需要代入 即可得到答案。

为了进行转移,我们额外定义 表示图 的最小生成树的最大边权小于等于 的概率,这也是一个关于 的多项式。

考虑计算 ,我们枚举这张图 上的 MST 的边权最大的边 ,这条边应该将图分成两个集合,不妨直接枚举这两个集合 (注意 应该为无序集合),那么此时有:

后者的意义为对于集合 和集合 枚举一条边连接两者且权值大于两者的和,这条边对答案的贡献为 ,同时连接 中的其他边的边权均大于这条边。

考虑计算 ,我们类似处理,这里根据 ,不难得到转移:

这里两张图的贡献合并需要注意顺序,实际上我们在计算 ,但是可以逐个合并答案。

先合并 的答案有:

这是一个新的平方项,此时考虑维护一次项即

然后和 合并即可。(方便表述设 为一次项, 为二次项)

考虑 ,类似的,我们枚举 MST 上最大的边权,同时枚举它将集合分成的两个子集,这两个子***附带一个概率,不难得到转移:

稍微归纳一下,不难发现 为关于 不超过 级别的次幂多项式。其中,边界条件为 中只有一个节点,此时 ,同理于

对于两类转移,不妨先求出后者关于 的多项式,然后通过积分表示成关于 的多项式,然后求和即可,不难观察出最高次幂不超过边数乘以 ,复杂度为

实际上这个多项式可能是 级的?不太清楚,反正上界是 就对了。

算一下感觉这个玩意儿非常不能过,实际上存在严格 的做法(预处理多项式的点值就可以了)然而在 的情况下这个做法的速度都几乎被 吊打,因为对于更小的状态多项式的次幂更低...最后测出来 的情况下的极限数据,只需要运行 次。( 的时候运行速度好像差不多?)

如果你写了 的做法大概也是可以通过的,需要略注意常数。(所以我把时限开成了 4s)

如果写 的算法大概是没啥问题的。

ps:这个做法可能可以拓展到更大的次幂,但是转移时计算量的增长倒是挺快的,出题人没有耐心算了,就单独拿了平方出题了。

G - solution

根据裴蜀定理,条件等价于 ,将所有数先和 ,对 进行质因数分解,对于某个 ,假设 在对应次幂上不高于 则标记为 ,否则为 ,这样每个 可以对应成一个二进制数

于是对于 的时候集合有贡献等价于 按位或的结果为全集 ,接着考虑 的情况。

表示集合 对当前 的贡献次数,那么不难得到 ,不难通过归纳法证明一个大小为 的集合 对答案的贡献为 。(二项式定理展开即可证明)

这样对每个位置选/不选列一个集合幂级数,定义运算为 ,那么可以得到答案为 为全集。

注意到点值只能为 ,计算有多少个 可以通过将所有 加起来得到的集合幂级数 做 FWT 得到,计算快速幂,然后 IFWT 还原即可,复杂度为 ,其中 表示 的质因子个数,本题中为 ,需要略注意常数。

全部评论
实名吐槽这场比赛。 C 数据锅了就算了,一个答疑从头到尾不回复真就离谱,还有这样的出题人?
7 回复
分享
发布于 2020-11-14 09:13
G题后面fwt的部分不就是黎明前的巧克力吗
3 回复
分享
发布于 2020-11-25 09:46
饿了么
校招火热招聘中
官网直投
u1s1这个G出的真的是秀,完全考到对FWT的理解。
2 回复
分享
发布于 2020-11-20 17:00
我有点没太懂出题聚聚D题动态维护树直径的方法,我是在每个点下挂新点后以欧拉序建线段树暴力维护树直径,由于修改随机,所以每次修改差不多是修改log次,总体复杂度nlog2. 但显然出题人的方法应该更优雅,可以讲得更清楚些吗?
点赞 回复
分享
发布于 2020-11-15 17:35

相关推荐

发个腾讯的吧,刚面完,以为是kpi,所以没录音,能写多少是多少点击查看详情自我介绍介绍项目1.java和其他语言的区别,比如c++,python,各个方面2.知道几种编程思想,比如面向对象等等3.知道的设计模式4.jvm结构、垃圾回收算法5.乐观锁CAS6.数据结构了解哪些7.排序算法呢,说一下快排,时间复杂度。空间复杂度8.计网1.OSI七层,作用2.http状态码,502如何查找排除3.http报文结构4.https的过程,三次握手,TLS四次握手等等,认证过程5.了解过哪些加密算法,什么是对称加密和非对称加密6.cookie和session了解过吗,区别,集群里,session在一个服务器,请求分配到了其他服务器,怎么解决这种情况说了一些以后,提示我想想redis、mysql7.websocket了解过吗,。。。。我不知道8.http有哪些请求方法,然后给我个场景,问我怎么解决,具体忘了,反正他最后引导我是用head(应该)9.ping用过吗,基于什么协议10.DNS解析过程、我还说了两种方法,递归,迭代,问我迭代体现在哪11.DOS攻击是什么12.TCP三次握手。四次挥手,各阶段的状态,为什么要三次握手、四次挥手,状态那还问我,SYN_RECV之前服务器是什么状态13.为什么要等待2MSL14.TCP   UDP区别、应用场景,问我,游戏用的是什么,腾讯会议呢?我答是QUIC,不晓得对不对15.我看你这是个前后端分离项目,那么跨域问题怎么解决。我不知道。。。。16.静态资源问题,后面提醒我用CDN17.TCP拥塞控制四个过程。TCP滑动窗口了解过吗,讲一下18.TCP、UDP格式操作系统1.内核态、用户态,切换方式2.进程线程,区别、协程了解过吗(协程不知道)3.一个进程,你发现cup使用率很高,你怎么排查,我猜与协程有关,就往这方面答了4.一个线程阻塞到这里了,你怎么解决,我还是从协程方面5.进程间通信方式。调度算法6.虚拟内存了解过吗7.分段分页的调度算法8.OOM了解过吗,怎么排查,怎么解决9.什么是死锁,如何避免、解决redis、mysql1.redis持久化机制2.redis的数据结构3.其他想不起来了。。。。字数超了 #腾讯# #腾讯一
点赞 评论 收藏
转发
12 收藏 评论
分享
牛客网
牛客企业服务