竞赛讨论区 > 【题解】牛客练习赛8
头像
牛客网小运营
编辑于 2018-12-27 14:52
+ 关注

【题解】牛客练习赛8

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 约数个数的和
答案就是
for( register int i = 1 ; i <= n ; i++ ) ans += n / i;
相当于枚举那个约数,查一下有多少个数有那个约数可以O( n )求也可以O( sqrt( n ) )求

T2 储物点的距离
维护几个前缀和,算算贡献就可以了
大家可以自己推推式子吧
O( n + m )

T3 回文串的交集
考虑容斥一下,求两个不相交的回文子串很好求
枚举一下分割线,然后严格属于两边的回文子串就可以产生贡献
大力差分一下,维护两个前缀和,算算贡献就可以了
O( n )

T4 加边的无向图
可以用并查集或者DFS或者BFS直接搞搞
答案就是联通块个数 - 1
O( n )

T5 集合中的质数
考虑容斥一下,然后直接求就可以了,因为所有数都互质
O( 2^n )

T6 重排的回文串
考虑一个区间可以重排为回文串,即其中最多只有一个字符出现奇数次
把’a’ -> 1 , ‘b’ -> 2 , ‘c’ -> 4 ... ‘z’ -> 2^25
这样等价于这个区间的xor和为2的整次幂
我们维护一个前缀xor和bi = a1 ^ a2 ^ ... ^ ai,然后等价于查询区间[l,r]中有多少点对(x,y)满足b[x-1]^b[y]为2的整次幂
这个明显可以莫队维护,复杂度O( 27nsqrt( n ) )
空间需要预先离散化所有转移之类的,反正乱搞搞就可以了
还有两种O( nsqrt( 27n ) )的做法,一个是分块然后预处理点东西,另一个是根号分治然后乱搞搞,不过我忘了我当时怎么做的了,所以就不介绍了吧

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

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

等你来战

查看全部

热门推荐