打(color{red}checkmark)表示有做
打(color{green}checkmark)表示有做,且写了题解
打(circ)表示尝试了,但是不会
打(color{yellow}checkmark)表示想过了,但是没有写代码(口胡了)
(* easy)表示较简单
(* medium)表示中等
(* hard)表示难
以上难度均指思维难度,主观性较强,与luogu,cf评分可能出入较大,不过luogu有一些比较早的CF黑题是真的水
没标难度大部分是上古时期在做题的时候无意中做到的,差不多忘光了
进度(19 / 50)
Part1.
- CF504E((color{red}checkmark))
- CF505E((color{red}checkmark))
- CF506E ((circ))(* hard)
- CF512D((color{yellow}checkmark))(* easy)
- CF516D((color{green}checkmark))(* easy)
- CF521E((color{green}checkmark))(* medium)
- CF538G((color{red}checkmark))(* medium)
- CF538H((color{green}checkmark))(* medium)
- CF547E((color{red}checkmark))(* easy)
- CF585E((color{red}checkmark))(* easy)
- CF553E((color{yellow}checkmark))(* medium)
- CF549E((circ))(* hard)
- CF555E((color{yellow}checkmark))(* easy)
- CF568E((color{red}checkmark))(* medium)
部分题目简要题解
如果是比较有趣的题会另外写题解,在这里挂链接,简单题就算了
- 由直径的性质,我们注意到(f_x)表示的是到直径两端点的最大值,我们令(v_x)表示(f_x = dis(x,v_x))
- 考虑直径的中点,如果以其为根,那么对于根的任一子树,任意点的(v_x)一定会在另一颗子树内,即子树内部的(f_x)随着与深度同增同减,即父亲的(f_x)一定严格小于儿子的(f_x)
- 如果直径的中点是一条边,那么取两端(f_x)较小的那个点即可
- 根据以上性质,可以线段树合并,直接查询,也许可以用并查集做到更优的复杂度
- 复杂度(O(qnlog n))
- 注意到上下左右走(x,y)互相约束,不好考虑
- 考虑转坐标系,用切比雪夫距离来代替曼哈顿距离,(x' = x + y,y' = y - x)
- 不等式约束计算一下即可
- 注意一下转移中因为 j 的值单调增加,所以转移是 DAG,用记忆化搜索即可
- 注意转移形式是一个半在线卷积,分治 FFT 即可
- 把边双联通分块缩点,定向成强连通
- 剩下的树上差分随便做就可以了