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

【题解】牛客练习赛9

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

T1 珂朵莉的假动态仙人掌
1 2 1 2 1 2 1 2地送即可

T2 珂朵莉的值域连续段
一个子树值域连续当且仅当其子树max-min+1=size
DFS一下即可

T3 珂朵莉的二分图
二分图即不能有奇环的无向图,要使得所有的奇环消失,即要删去所有奇环的交上的边。
但是如果删去奇环和偶环的交上的边,奇环和偶环就会重新组成一个新的奇环,所以在偶环上的边是不能删的。
先随便搞个生成树出来,然后对于每个非树边在树上打标记,最后DFS一次即可以实现O( n + m )

T4 珂朵莉的假toptree
暴力

T5 珂朵莉的数论题
当p>=x时,可以用1e9/x的筛算出来答案
当p<x时,考虑二分答案ans,然后容斥即可验证
x在60左右的时候最快

T6 珂朵莉的约数
对每个数进行质因子分解,考虑一个数的约数个数即为其每个质因子出现次数+1的乘积,所以维护这个即可
考虑每个数只有一个大于1000的质数,对这部分进行根号分治
对于小于1000的质因子(只有168个),维护一个前缀和pre[i][j]表示第i个质因子在前j个数中出现次数
对于大于1000的质因子,用莫队维护即可
总复杂度O( nsqrt( m ) + ( n + m ) sqrt( v ) / logv )

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

全部评论

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

等你来战

查看全部

热门推荐