竞赛讨论区 > 牛客练习赛 92 题解
头像
dottle
发布于 2021-11-26 22:06
+ 关注

牛客练习赛 92 题解

A

平均数为 ,即数列的总和为 。那我们构造数列包含 ,剩下一个

数据范围保证了一定有解。

B

对于输入的 ,我们可以在处理时去掉他们,只需最后将其全部放入某一个集合即可。

如果 ,只需判断所有数的总和是否为

如果非零元素的个数小于 ,则显然无解。否则一定可以构造出解,下面介绍一种方法:

个分别非零元素放入 个集合,对于剩下的数和剩下的两个集合,若全是正数或全是负数,怎么放都合法;否则将正数放入第一个集合,将负数放入第二个集合。

C

正向考虑困难,我们考虑反情况,即不存在相交边。

这时候方案数为(当然式子不唯一)
$$
那么直接计算这个,从总方案数减去这么多就是最终的答案。

D

如果一个点与两个关键点相邻,则若 D 走到了这个点就一定能走到关键点,所以可以将其视为关键点。

我们 bfs 处理哪些点可以视为关键点,最后判断 1 是否可以视为关键点就可以了。

E

当取 时,答案可以取到奇数和偶数中的较多者,换言之,答案的下界为 ,这启示我们可以使用随机化算法。

我们定义检查一个数为将其作为 ,计算答案最大为多少,此操作的复杂度为 。(前者使用数组作为桶,后者使用 map 作为桶)。

计算答案时,我们从数列中随机两个数,则他们同时处在答案集合的概率不小于 。然后求出他们的差,检查差的所有因数。容易发现,若选的两个数同时处于答案集合,则我们此次检查可以求出答案。重复 次,出错概率仅为 ,可以通过此题。

为了通过此题,可能还需要考虑一些复杂度优化上的问题。第一是我们筛出所有质数,每次求因数时只用质数去筛,这样可以保证检查以外部分的复杂度足够低;第二是注意到 互不相同,因此在检查的时候,我们根据当前的答案 ,先判断是否有 (注意这里可能爆 long long,可以用 double),若否,则说明当前的 不可能成为答案,直接跳过即可。

试着分析复杂度,先看检查部分,加上记忆化后,此部分复杂度之和为 (即将可能成为答案的质数全部扫一遍),因为有 ,故此部分复杂度上界为 ;又因为我们的复杂度是 代表 不同的质因数个数)的,所以这一部分的真正复杂度是 的。寻找质因数部分的复杂度显然是 ,仔细分析发现最大的取模次数也只有大约 次,加上随机化造成的小常数,可以通过这道题。

F

这个图显然是平面图,由欧拉公式,黑连通块数 = 黑点数 - 黑边数 + 黑环数

黑点、黑边都可以排序 + 双指针求出数量(比如竖边相当于 ),黑环数呢?分成两类:四元环、非四元环。四元环计数可以用相同的方法()。非四元环呢?

结论:黑非四元环数等于白连通块数减一。

证明:除了最外面那一圈连通块,其他内部的白连通块一一对应一个黑非四元环。有一种例外是出现不封口的情况,如图:

##.
#.#
###

里面的白孤立点没有对应任何黑环,但注意到只要 ,一定有 ,所以这种情况不可能存在。(也就是说只要一个长方形有两个对角是黑的,一定会有三个角是黑的)

所以黑连通块数 = 黑点数 - 黑边数 + 黑四元环数 + 白连通块数 - 1,也就是黑连通块数 - 白连通块数 = 黑点数 - 黑边数 + 黑四元环数 - 1,由此式就可以求出答案了。

要求答案和,用期望线性性拆开分别计算即可,非常简单,这里只以四元环数为例推一下:

这个式子可以 计算,具体的方法是把 min 拆掉,然后把多项式拆开,用自然数幂前缀和计算。

黑点和黑边的推法类似,这里不再赘述。

全部评论

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

等你来战

查看全部

热门推荐