ds做题记录

chenzhiyv · 2025-06-17 21:17:32 · 个人记录

CF593D Happy Tree Party

有 \lfloor \frac {\lfloor \frac {a}{b} \rfloor }{c} \rfloor = \lfloor \frac {a} {bc} \rfloor

所以只用查乘积即可

注意边权下放点权是两点之间的路径权值之和（乘积等）不算LCA

P4092 [HEOI2016/TJOI2016] 树

与CF342E Xenia and Tree一样，类似根号重构（或者说对操作分块），先将修改放在一个数组中，当达到一定量时就全部更新在树上

CF208E Blood Cousins

dsu on tree

思想：

暴力时，每一次都需要清空，费时间，将最大的子树放在最后清空，类似重链剖分，划分轻重儿子，轻儿子清空，重儿子不清空，具体见代码。

CF246E Blood Cousins Return

与CF208E Blood Cousins一样

CF341D

类似二维区间和，用树状数组，转化为差分数组，注意在四个位置加减，以及加减时是否包括当前这个位置

CF840D

莫队处理出现次数，再加上随机化，就可以了

CF442C

首先，在下次遇到这种题时，注意到值与两边有关，所以关注增减性，画出增减性图像，结合样例的最优方案可以得出先删 V 字底，在画出删完后的图像，观察到取不到最大值和次大值，所以最优就是其余全部数取一遍。