louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共5篇）

题解 | 算法竞赛进阶指南疫情控制

思路显而易见,答案具有单调性,时间越长,越容易控制疫情.所以很容易想到二分时间.首先,占据一个点肯定不如占据这个点的父亲,因此时间内到达不了号节点的尽力往上跳就可以了(暴力跳可不行,需要使用倍增).还有一些军队可能会经过号节点到达其他号节点的儿子节点.先来证明一个结论:若些军队的集合不经过号节点能...

树上倍增

2019-08-27

1 760

题解 | 算法竞赛进阶指南雨天的尾巴

思路好恶心的卡常题(虽然一边颓废一边写,还是卡了一下午).如果空间和时间足够大,我们可以考虑对每一种粮食开一个大小的数组,若某条路径放类型的粮食,,树上前缀和,然后找出最大值即可.不过这样就算是离散化后,时空复杂度都是.不过这样直接把开的数组改成动态开点线段树就好了.求前缀和的过程可以看成线段树合...

线段树前缀和树上倍增

2019-08-22

0 619

题解 | 算法竞赛进阶指南异象石

思路我们需要把所求的东西转换一下.容易想象,取出所有节点建一棵虚树(放心,不用真的建,只要知道是什么就OK.也就是将所有节点以及两两之间的(以下称为关键点)取出来建树,若两个关键点之间的路径没有其他关键点,就将这两个关键点之间连边,长度为两个关键点的距离),虚树所有边长度和即为答案.想象遍历这颗虚...

树上倍增

2019-08-21

0 707

题解 | 算法竞赛进阶指南闇の連鎖

思路删去一条树边能把树断成两个联通块.未删去的非树边不能把两个连通块再连回去(否则不是白搭了2333).如果一条非树边与树上的边构成一个环,删去这个环的树边的同时,必须将这两条边同时删去.如果某条树边同时在好几个环中,肯定不能删去这条树边,因为只能删一条非树边,删了条非树边,剩下的还是连通.对于一...

树上倍增前缀和

2019-08-21

0 509

题解 | 算法竞赛进阶指南次小生成树

思路先建出最小生成树,然后考虑删去树上一条边,加入一条非树边.枚举一条非树边加入,然后需要选出树上节点,之间的路径的一条边删去.很明显,删去的边应该越大越好,但是不能与边相等,否则就不是严格次小了,因此需要求出树上路径边权的最大值和最小值,可以使用倍增LCA解决qwq.最生成树复杂度为,寻找替换边...

树上倍增

2019-08-21

0 652