竞赛讨论区 > 【题解】牛客挑战赛 52

【题解】牛客挑战赛 52

头像
YLWang
编辑于 2021-09-18 09:46:16 APP内打开
赞 7 | 收藏 1 | 回复2 | 浏览874

A 深海少女

签到题。按照题意把每个位置放的数对答案贡献的系数算出来。从大到小排序填数即可。

B 天平

签到题。直接做树形背包, 表示子树 重量和为 的最小杆长。然后大力转移即可。

C 随机字符串生成器

发现第二个生成器只比第一个生成器增加了稳定性,即相同字符之间的距离更加稳定。所以在统计数据中找一个描述稳定性的即可,包括但不仅限于方差,最大值,最小值。

D 小 L 与 GCD

假如不求子序列下标乘积和,只求具体 的值的时候,我们有一个直观的想法:枚举 ,设为 ,计算有多少个子序列满足 .

注意到满足 这一条件的子序列个数不太好计算,但是满足 这一条件的子序列很好计算。因为后一条件等价于每一个数都是 的倍数,所以就有 这么多个,可以在 的复杂度内预处理。所以利用容斥 可以在 的时间内计算出对于所有 ,满足 这一条件的子序列个数。

上述做法实际上给予了我们一些启发。因为满足 这一条件的子序列的下标乘积和也是很好计算的。也就是令满足 集合为 ,那么贡献就是 ,也可以在 的时间内进行计算并进行容斥,计算出满足 这一条件的子序列的下标乘积和。

接着我们从大到小枚举 ,这样就可以通过以上两条信息计算出第 的子序列具体 是多少,设为 。整块的答案已经计算完毕,所以我们只需要计算 的子序列里字典序前 小的子序列乘积和。

我们采用一种比较暴力的方法:挑出所有满足 ,然后暴力进行 dfs. 每找到一组方案就 k--,直到 退出程序。

复杂度正确的原因在于,每进入一次 dfs 定会找到一组 的子序列。而根据我们上述的计算过程可知, 的子序列总共就不超过 个,且每次访问到 的子序列都会导致 减小 ,所以到达 时 dfs 的次数将是 级别的。

所以我们就可以解决这个问题,复杂度瓶颈在于第一步的容斥,所以复杂度为 .

注意到 高达 ,暴力的复杂度为约 1e8 量级,经过常数因子的制约很容易被卡常数。

而对于每一步,实际上都可以写成因子层面的高维前缀和与差分。所以我们可以使用该技巧进行优化,复杂度为 此时复杂度受 制约,是一种更优的做法。

E 图同构

我首先声称 是有解的下界,那么想法是构造一个 的满足条件的图,然后在它上面略作修改。

发现并不容易找到一个对于任意节点 的图,所以考虑先构造满足这个限制的图。

一个想法是找到一个满足限制的环,然后在环上的一个节点挂一条链,所以考虑先构造一个 的环。

发现问题在于需要破坏环的对称性,例如轴对称,循环移位等。此时剩余操作空间很小,手构是容易的。即使真的构不出来,也可以爆搜。最后得到的图长这样:

图片说明

此时找到一个与他不同构的图是容易的(对换 两边):

图片说明

然后只需找一个节点挂链即可,注意 不能作为挂的根节点。

最后答案如下:

图片说明

至此仍有一个问题是如何说明 是有解的下界,简单爆搜即可。

F 年少有为

这是一道改编题。容易发现其不弱于 CF1458F Range Diameter Sum。

首先你需要熟练掌握 CF1458F 的做法。这里不予赘述。

下文认为 ,求 LCA 的复杂度为

先考虑块内怎么做。发现随机数据下,每个块内点个数期望是 。不妨对每个块 枚举端点。

在枚举左下角的时候,可以扫描线,用 BIT 维护当前 坐标下 坐标区间的直径。这样是 的。

之后考虑如何将一维做法扩展到二维。基本的想法是类似地直接对块分治。

一维时分界线右移是因为有重要性质:右移时点集单调递增,只加不减。因此想到二维偏序剖分。

现在我们的问题就是要把若干个点分成尽可能少个二维偏序组,满足每个点在恰好一个组中。

于是他就是一个最小链剖分。最小链剖分=最长反链,所以组数是 LIS 长度。随机数据下 LIS 长度期望是接近 的。于是复杂度就对了。

具体如何剖分?开 LIS 长度个坑,每次贪心放置就好。

2条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐