牛客练习赛77官方题解

T1
签到题,等差数列求和O(1)输出即可

T2
类似的思路,我们发现约数的条件我们也是可以转化成倍数的
这样就是考虑x的倍数在n之内的数的求和,我们同样可以用等差数列求和来求出来

T3
容易发现我们的这个函数G(n)=sum i=1..n i*n/i
这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件,因此还是转化成倍数问题
于是这个我们其实可以用整除分块来优化
推荐一个博客:https://www.cnblogs.com/peng-ym/p/8661118.html

T4
本题我们用一种折半思想类似折半的思想来做
相当于我们枚举一位,然后另外一位用meeting in the middle做
但是我们还需要减掉一些重复的情况,这个很好推导具体可以见代码
于是我们发现这样我们就可以hash了
但是这题我们的unorderedmap过不了,因此需要手写哈希。
时空复杂度:O(N*30)
注意hash的复杂度是O(1)的

T5
容易发现我们暴力N^2建图跑割点正确性是对的
因此我们下一步目标是如何优化建图
显然,这道题 tarjan 算法是必须使用的。
tarjan 算法的复杂度就是图的大小。
我们发现可以在值域下手
于是我们发现这个gcd和其他约数没有关系,我们只需要考虑质数
显然这个范围是可以接受的
因此我们每次像质因数连边,然后在无向图上缩点,判断强联通分量就可以了
这样我们只需要对每个点的出边考虑就可以了
但是我们需要注意的是要判断一下单独一个点的情况,很多人好像都WA在这里了
容易发现我们建图后的规模是可以接受的
时间复杂度O(Nsqrt(N))或者O(N log N)

T6
由于latex的原因在这里看吧orz

另外:撞了快艇下大雨我同学的验题账号,大家不要在意orz

代码:
全部评论
请问您T4 std 里面的chek函数怎么证明复杂度正确呢?
点赞 回复
分享
发布于 2021-02-27 06:02

相关推荐

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