UOJ Logo root的博客

博客

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180114#007

2018-02-08 10:37:25 By root

背包

首先按价格从大到小排一遍序。

考虑跳着跳着走,每次先二分出能买的最大价格的物品的位置,走过去、

之后二分出能买的一段物品(用前缀和记录),减钱并购买之,跳到那一段的末尾。

之后再重复第一步,不断地一段一段走即可。

这样的时间复杂度为 O(MlogNlogN) 。

因为一个人的钱数每次至少减少一半(价格从大到小,不然就还能再买),

这样就最多二分 log 次,复杂度得证。

字典序

若 A i 排在 B i 前面,就 A i 向 B i 连一条有向边,这样就构成一个 DAG 。 那么做一遍拓扑排序,用一个小根堆存着,每次取最小,再把入度为零的点加入堆中即可。使用优先队列实现即可。 时间复杂度 O(N log N)

最长树链

枚举所以质因子,然后dfs的时候只走有当前这个质因子的点。。。这样的话正面看来复杂度貌似很大,最多有10W个质因子,每次dfs复杂度上限也是10W,,貌似会超时? 这个时候要从另外一个角度计算复杂度啦。我们对一个数来考虑,他会被几次dfs遍历到?。很显然就是它的质因子的数量次,,一个数的质因子数比logn还要小很多。所以所有数只会被遍历到最多 nlogn次,复杂度也差不多nlogn级别的,就不会超时了。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。