【题解】牛客小白月赛18

A.Forsaken喜欢数论

很显然, 可以在线筛过程中维护出来,所以我们只需要做一遍线筛维护出所有 ,然后求和就行了,复杂度 .

B.Forsaken喜欢字符串

对于每个询问,本质上是求其他所有串的长度为的子串是串的子串的个数,然后总数乘上就是答案,注意到特别小,因此我们只需要存下每个串的所有哈希值,并且记录这个哈希值出现的次数,然后每次查询哈希值出 现的次数就行了。复杂度是

C.Forsaken给学生分组

签到题,我们将数组排序,然后取最大的个之和以及最小的个之和,相减就是答案。复杂度


D.Forsaken喜欢正方形

简单计算几何,对于第一种情况,只需要会判断4个点能否构成正方形即可。
对于第二种情况,只需要枚举四个点,然后依次判断移动后能否构成正方形。
前两种都不行就是第三种。

E.Forsaken的数列

简单数据结构题。考虑这个题有动态插入点这个操作,因此我们很容易想到维护序列操作,因为我不擅长 ,所以提供一个无旋的做法。
对于操作1,我们只需要分裂出的子树,然后插入点合并就行了。
对于操作2,在无旋区间的子树打上就行了。
对于操作3,取无旋区间的和就行了。
复杂度

F.Forsaken的位运算魔法

类欧几里得算法套路题。我们对按位考虑,当的二进制第位为时,那么当且仅当的第位为1时才有贡 献。那么对于第位我们只需要计算有多少个满足第位为1,这等价于计算的值。对于,我们枚举每一 个,然后问题就转换成对于所有 ,这是个经典的类欧几里得算法形式。
现在考虑第位为1的情况,那么问题转换成计算位为0时的贡献,那么我们转换成总数减去第位为1的个数就是答案。复杂度是, 是一个非常大的常数。

G.Forsaken的三维数点

简单二分 + 树状数组统计。对于每个我们都可以算出距离原点的位置,然后我们把贡献算在这个距离向上取整的位置上。查询的时候只需要二分距离,然后树状数组统计这个距离内的能量和。复杂度是


H.Forsaken喜欢独一无二的树

最小生成树统计冲突边。考虑问题形式我们可以转换成删掉所有可以代替最小生成树种某条的边的所有边权和。 一个比较笨的做法是树上倍增,我们找出一颗最小生成树,然后枚举每条不在树上的边,判断两端路径上的最大边是 否大于这条边,复杂度是
比较好的做法就是我们在构造最小生成树的时候直接计算每条可以加进最小生成树的边权和,然后最后减掉最小 生成树的边权和就是答案。复杂度是

I.Forsaken遇到了毒瘤

我们从这个限制入手。
众所周知,,那么限制转换成.
两边同除可得 .由于这个式子有天然的限制.
同理可得。由此可见的取值只有
那么对于和式.我们写成。设,可以发现是个经典的数论函数求和,我们预处理出函数的前缀和,然后整除分块就可以求这个积性函数和。那么有了,我们可以把答案写成。复杂度是


J.Forsaken喜欢玩自走棋

我们设。那么这个题就是求最大的和对应的。 显然有一个显然的枚举子集的做法,复杂度是,考虑到这个题的最大可以到,所以这么做显然会。 我们考虑,这个问题就是典型的问题,直接反着写的转移就行了。复杂度是是二进制最高位。
全部评论
点赞 回复
分享
发布于 2019-10-26 22:22
点赞 回复
分享
发布于 2019-10-27 01:35
英特尔
校招火热招聘中
官网直投
点赞 回复
分享
发布于 2019-11-13 17:46

相关推荐

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