0%

March

三月的做题记录

三月的做题记录

CF1648E Air Reform

TAGS:Boruvka,克鲁斯卡尔重构树

我们考虑直接建出补图的最小生成树。

看到隐式图的最小生成树构建,想到 Boruvka 算法。那么技术难点就在于如何给每个点找一条最小的出边。一个直接的想法是先用线段树维护每个点是否可选,然后在克鲁斯卡尔重构树上倍增,但是这是 $\log^3$ 的。考虑倍增过程对 DFN 区间的影响,可以发现本质上是在找 DFN 序中的前驱与后继,那么改成线段树二分即可。

Luogu5591 小猪佩奇学数学

TAGS:单位根反演

复习一下单位根反演:$[k|n]=\dfrac{1}{k}\sum\limits_{i=0}^{k-1} \omega_{k}^{in}$

然后利用 $\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$ 来构造递推关系,再瞎推推式子就行了。

CF1648D Serious Business

TAGS:DP,线段树优化

前缀和之后可以将答案写成这个形式:$\max\limits_{1\leq l\leq r \leq n} {f_l+g_r-cost(l,r)}$,其中 $cost(l,r)$ 是覆盖 $[l,r]$ 区间的最小花费。

考虑设 $dp(i)$ 表示选择一个切入点 $l$ 累加上 $f_l$ 的贡献,然后走到 $(2,i)$ 的最小花费(钦定 $i$ 处有一条线段结束)。转移大概就考虑加入了哪条线段,以及切入点是否在最后一条线段里,可以线段树维护。

然后枚举最靠右的线段,也可以线段树计算。

HNOI2022模拟测试三十八 取数

TAGS:min25,矩阵乘法

考虑单独计算 $f(x)$ 时可以 DP,将 DP 写成矩阵乘法的形式后可以发现乘上的每个矩阵跟分解的 $p_i^{c_i}$ 有关,是积性函数!那么考虑 min25 筛,在计算质数处前缀和的时候可以直接计算质数前缀和和质数个数前缀和,然后递归 min25 的时候因为每次是取出最小的质因子,不会受到矩阵乘法无交换律的影响。

ZR省选十连测Day7 C

TAGS:FWT,多项式

一个暴力做法:设 $F_i$ 表示选了 $i$ 个不同位置数的异或集合幂级数,$H$ 为原序列的桶的集合幂级数,则有 $F_i=F_{i-1}\times H-(n-i-2)\times F_{i-2}$。那么最终 $F_m$ 将会是一个关于 $H$ 的多项式(异或卷积),我们可以用分治 NTT 求出这个多项式。然后对 $H$ FWT,然后再做一个多点求值。

考虑原问题要求的是从 $n$ 个集合幂级数中任意选出 $m$ 个乘起来然后求和。考虑对每个幂级数 FWT 后,每一位都只会是 $-1$ 或 $1$,那么我们只需要对于任意的 $a\in[0,n]$ 计算出 $x^m^a(1-x)^{n-a}$ 就行了。直接卷积即可

我们考虑对这个东西分治。在分治树上游走的时候,如果往左边走就乘上一个 $(1-x)^{r-mid}$,往右走就乘上一个 $(1+x)^{mid-l+1}$。这样子走到叶子的时候就是目标多项式。注意到我们只需要第 $m$ 项的系数,而当前在分治区间 $[l,r]$ 时,我们的多项式在走到叶子时至少还要位移 $\lfloor \frac{r-l+1}{2} \rfloor$ 项,因此只保留后这么多项即可。至于如何计算要乘上的多项式,考虑分治树的区间一层只会有 $\mathcal O(1)$ 不同的区间长度,因此可以直接暴力求。被直接卷积吊起来打

ZR省选十连测Day7 B

TAGS:随机的性质,SegmentTreeBeats

考虑一个随机的性质:对于一个长 $n$ 随机的数列 $a$,其期望最长不降子序列是 $\mathcal O(\sqrt{n})$,因此我们可以将询问的操作左界 $l$ 排序,然后按 $r$ 划分,划分出 $\mathcal O(\sqrt{n})$ 个集合,其中每个集合里的操作区间有嵌套包含关系(一条链)。

然后就可以对于每个集合用 SegmentTreeBeats $\mathcal O(n\log n)$ 算出所有答案了,总复杂度 $\mathcal O(n^{1.5} \log n)$。

HNOI2022模拟测试三十六 打麻将

TAGS:贪心,线段树

对于单次询问考虑一个贪心策略:优先考虑深度较大的点为 LCA 的路径,如果子树内能选出两条长度之和大于等于 $k$ 的链则直接选取,这个点及其子树以后将无法对答案再产生贡献。因为一个点至多处于一条被选取的路径中,因此是正确的。

再注意到一个关键性质:所有询问的答案之和是 $\mathcal O(\sum\limits \dfrac{n}{ik})=\mathcal O(\dfrac{n\ln n}{k})$ 级别的,这启发我们寻找复杂度与答案大小相关的算法。

考虑维护一个当前子树内可能产生贡献点的集合,每次从其中选出一个最深的点,判断其子树内直径是否大于等于 $k$,如果是,则将整个子树打上 $+1$ 的占用系数,并且向上倍增跳到第一个子树内直径大于等于 $k$ 的点,将其加入集合。采用线段树来维护直径。注意我们只能提取出占用系数为 $0$ 的点,而要维护这个必须满足一个条件:一次操作要么是新加入的要么等价于撤销之前一次被加