竞赛讨论区 > 牛客挑战赛60 题解
头像
stoorz1023
发布于 2022-05-13 22:37
+ 关注

牛客挑战赛60 题解

A 第三心脏

,问题等价于需要找到一个最小的 a 的倍数 c,使得
若质数 p 并非是 b' 的因子,那么 就是一个合法的解,那么只需要枚举出最小的 p 即可。而前 13 个质数相乘已经超过 ,所以只需要枚举前 12 个质数。
时间复杂度 。其中 V 是值域。

B 尖端放电

考虑到当一个点被攻击第二次时我们就找到一个答案了,否则会至少覆盖一个新的点,所以直接暴力枚举所有点对直到找到答案即可。
时间复杂度 O(Tnm)

C 格点染色

f(x) 为把前 x 个格子染成黑色的顺序方案数。考虑这 f(x) 个方案中的一种:
  • 如果 xf(x) 中是最后一个被染色的,那么方案数为 f(x-1)
  • 如果 xf(x) 中不是最后一个被染色的,在 f(x-1) 中,对于 ,令 zy 前一个染色的点,那么有 ,因此可以把 x 放在 zy 之间染色,y 是第一个染色的点时同理。因为 y 共有 x-a_x 个取值,所以方案数为
综上,总方案数为
时间复杂度 O(n)

D 三千道路

一张竞赛图中两个点有三连通关系:
  1. a 能到达 bb 不能到达 a
  2. a 不能到达 ba 能到达 b
  3. a 能到达 bb 能到达 a
首先我们把强连通分量缩起来,如果有大小为 2 的需要输出 NO。之后一张 DAG 合法当且仅当它的拓扑序唯一。
充分性:当它的拓扑序唯一时我们之间前面的强联通分量都向后面的连即可。
必要性:若它的拓扑序不唯一,那么我们一定能找到两个强连通分量使得它们之间无法互相到达。
所以跑拓扑排序的时候判断是否任意时刻队列大小不超过一即可。
时间复杂度

E 字典树简单题

有一个显而易见的结论:对于任意一个节点 x,以及两个叶子节点 y_1,y_2,若满足 ,那么 xy_1 的权值一定大于 xy_2 的权值。
证明的话,考虑 x 与它父亲 fa 的边的权值 v。如果 ,那么 深度越小,xy 的权值在二进制表示下的位数就越多。如果 ,那么 fa 到另一个儿子的权值一定为 1,同样满足 深度越小,xy 的权值在二进制表示下的位数就越多。
所以说其实只需要找到 x 的深度最大的祖先,满足该祖先子树内的叶子节点数量不小于 k。然后答案一定就在这个祖先的不包含 x 的子树内。
可以用 LCT 维护每个点子树内叶子数量。对于加点操作,只需要把点 x access 后,将整棵 Splay 打上加的标记。
对于询问操作,将点 x access 后,相当于需要在这棵 Splay 上找到中序遍历最大的点满足子树内叶子不小于 k,直接在 Splay 上二分即可。那么只需要再支持查询点 x' 子树内,权值第 k' 大那个叶子。
如果没有加点操作,那么可以将叶子按照 dfs 序排序,然后对于 01 Trie 上的每一个点记录它子树内 dfs 序最小的叶子节点。那么 x' 子树内编号最小的叶子的编号 就是答案点的编号。
有了修改操作后,注意到加点并不会影响其他叶子排名的相对顺序,所以相当于需要支持在序列中插入一个数,并动态维护 01 Trie 上每一个结点子树内排名最小的叶子的编号。为了方便,下文称一个点 x 子树内排名最小的叶子的编号为 x 的最小叶子。
在序列中插入一个数这个很简单,再用一棵平衡树维护序列即可。
对于 LCT 上的每一个点再维护一个值表示 01 Trie 上这个点的最小叶子。考虑一次加点操作的影响。首先新加的点的子树内只有新加的叶子,而对于原本就在 01 Trie 上的点 p,它的最小叶子会改变成新叶子当且仅当:
  • px 的祖先。
  • x 与新建点之间的边的权值为 0,且 xp 之间的边权值均为 1
而 “xp 之间的边权值均为 1” 等价于 ”xp 路径上所有点的最小叶子均相同“。所以其实一次加点操作的影响,就是 x 到“满足最小叶子等于 x 的最小叶子”的祖先 p 这一段路径。
可以在 Splay 上二分找到这个 p 点,然后就是路径覆盖了,直接打标记就好。
维护好每一个点的最小叶子后,询问时只需要在平衡树上查询最小叶子的排名 rk,然后再查询排名为 的点即可。
时间复杂度

F 再见***与胖头鱼

当上次和这次攻击的胖头鱼不同时才会加一次攻击,显然所有胖头鱼都是一样的,所以我们可以只考虑一只胖头鱼造成的期望伤害。
构造多项式 F(x) 其中 表示一只胖头鱼被连续攻击恰好 k 次时的概率。
考虑到转移到下一条鱼时的概率是由上一条被攻击的连续次数决定,所以这个概率在每个 F 处乘上。
首先指定一只胖头鱼计算它的期望伤害,定义多项式 H(x) 其中 表示不是我们指定的胖头鱼被恰好攻击 k 次后就转回我们指定的胖头鱼的概率,那么有

那么多项式 H(x) 就可以用来表示被指定胖头鱼两次被攻击间的概率。
然后我们枚举破坏圣盾的次数,那么造成的伤害( 且不考虑初始的 8 点攻击力)就是
表示攻击了 j 次且破坏了 i 次圣盾时的概率,那么答案就是

考虑用多项式计算 ,首先我们开始时可能有一段不是攻击指定胖头鱼的,这一段就是 ,然后中间 j 段攻击胖头鱼的,且出了最后一个都需要一段间隔将两次隔开。
由于最后一段就结束了,此时不需要算上转移到另一条鱼上的概率,所以还需要一个 表示连续攻击一条胖头鱼 k 次的概率。
那么 f_i 的多项式就是

然后转到求答案就是

用等比数列的通项公式可以化为

多项式计算即可。时间复杂度

全部评论

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

等你来战

查看全部

热门推荐