「CF1229X」Codeforces Round #588

2019年10月3日3590

A. Marcin and Training Camp
若A觉得自己没有B强,B向A连边

度数为 0 的点,是觉得自己比其它人都强的,把它们依此拓扑排序删除

B. Kamil and Making a Stream

从一个点向上走,区间 gcd 单调下降,且最多变化 log 次

可以用树上倍增维护区间 gcd,枚举每个点往上二分跳,暴力统计答案

更简单的做法是用 vector 维护一个点往上的不同 gcd,以及它们贡献答案的次数,这个 vector 大小是 log

dfs 暴力往儿子转移

倍增:

dfs:

C. Konrad and Company Evaluation

给无向图定向,权值小的连向权值大的,答案是每个点的入度乘以出度求和 每次修改其实是把一个点的所有出边改成入边,暴力修改感觉卡不掉 实际上用势能分析可以证明复杂度 n√n

avatar
  Subscribe  
提醒