2021.10做题记录

P5243 [USACO19FEB]Moorio Kart P

考虑容斥,先把可能的算出来,然后再算 \(<Y\) 的
第一部分就直接把所有边权枚举出来乘一乘
\(<Y\) 的不难发现可以 dp
但是朴素的 dp 是 \(\mathcal O(n^3)\) 的
因此考虑根号分治
对于 \(n_i\leq \sqrt Y\) 的,这样的我们枚举每一个不同的边的长度,复杂度为 \(\mathcal O(n_i^2Y)\)
对于 \(n_i > \sqrt Y\) 的,这样的最多只有 \(\sqrt Y\) 个,复杂度为 \(\mathcal O(Y^2\sqrt Y)\)
第一类,根据均值不等式,所有 \(n_i\) 取 \(\sqrt Y\) 的时候复杂度最高,为 \(\mathcal O(Y^2\sqrt Y)\)
于是这道题目就愉快的在 \(\mathcal O(Y^2\sqrt Y)\) 的时间里解决了
但是一个坑点是边权可能为 0,所以判断的时候可能会出问题,因为这个调了一个多小时

code

CF1580D

发现这个式子长得特别奇怪,拆一下变成 \(\sum a_{b_i}+a_{b_j}-2a_k\)
建出一棵笛卡尔树,这个 \(a_k\) 就是他们的 lca
直接树形 dp
\(\mathcal O(n^2)\)

code

CF1580B

这个东西本质上是深度为 \(k\) 的点恰好又 \(m\) 个的 \(n\) 个点的笛卡尔树
所以直接 dp,\(f[i][j][d]\) 表示 \(i\) 个点 \(j\) 个深度为 \(k\) 的点,当前深度为 \(d\)
答案是 \(f[n][m][1]\)

code

上一篇:【学习笔记】光速幂


下一篇:CF1574F Occurrences