做题记录

就是各种套路，遇到了就记录一下吧
dp

容斥

硬币购物

题意：有四种钱 \(c_i\)，有数量限制 \(d_i\)，问凑 \(s\) 元的方案数
没有约束就是完全背包，有约束的话就减去已经拿了 \(d_i+1\) 的方案数，然后发现会多减，需要容斥
ds

分治

静态树的三度化

在各种树分治中都还是很常见的，就讲一讲，
一个点 \(u\) 的儿子集合为 \(son_u\)
我们构造若干个虚节点 \(v_1\cdots v_n\)，其中 \(n\) 为 \(son_u\) 的大小
进行重新连边

\[\begin{align*}s_i\in son_u\\s_i\rightarrow v_i\\v_{i+1}\rightarrow v_i\\v_1\rightarrow u\end{align*}\]
也就是搞成一条链的形式，然后把原本的儿子挂到链上，也可以写成线段树一样的递归写法，有时候常数会小一点，不过挺难打的
树上启发式合并

放到分治里面是因为 \(dsu\ on\ tree\) 能够解决的问题和分治类似，并且分析也是差不多
举例

一个大小为 \(n\) 的有根树的点有颜色，求每个子树内有多少不同的颜色，\(O(n)=10^6\)

最暴力的做法是用桶维护答案， \(O(1)\) 求出叶子答案，然后从叶子一路合并到根就做完了，但这样是 \(O(n^2)\) 的
因为只需要答案，所以可以选择直接继承重儿子的桶用来存答案，然后发现一个点的合并次数等于其到根路径上的轻边数，于是就是 \(O(n\log n)\) 了

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！