|
一道好题。
这是一个树形结构,我们可以先拍成 $dfn$ 序,然后对于每个星球,本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间,因为最多 $n$ 个操作,所以区间最多 $\mathcal{O}(n)$ 个,线段树分治,把这些区间插入,然后我们考虑如何求答案。
$y,z$ 是没用的,最终答案即为 $(x_0 - x)^2 + c$,拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。
我们考虑斜率优化,在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$,移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$,即点 $(x,x^2 + c)$ 斜率为 $2x_0$,维护下凸包即可,若二分则复杂度是 $\mathcal{O}(n\log^2{n})$,只需将 $x$ 与斜率 $x_0$ 都从小到大排序,我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。
题目2305 [CTSC 2016]时空旅行
![]()
2024-09-14 23:09:32
|
|
首先可以不是简单路径,这启示我们用并查集,但 $a,b$ 的二维限制有些不可做,我们可以先想暴力,对于每个询问只需将所有 $a_i \leq a$ 且 $b_i \leq b$ 的所有边加入并查集,并维护最大 $a,b$ 值,判断 $u,v$ 是否在一个联通块内,且最大值即为 $a,b$,这样可以 $\mathcal{O}(mq\log{n})$。
限制太特殊了,我们考虑分块,首先将所有边按照 $a$ 排序后分块,每个询问离线下来后把其放到尽量右块内,使所有其左边的块的 $a$ 值都小于等于它,然后我们枚举每个块,将该块询问先按照 $b$ 排序,再将前面的块按照 $b$ 排序,双指针加边即可。
对于在该块内的边,我们暴力枚举加边,枚举后撤销这些操作,所以 并查集不能路径压缩,只能按秩合并。
复杂度 $\mathcal{O}(qB\log{n} + \frac {m^2} B \log{n})$,取 $B = \sqrt{m}$ 得复杂度为 $\mathcal{O}((q + m)\sqrt{m}\log{n})$。
但是貌似 $B = \sqrt{m\log{n}}$ 跑的最快 : )。
题目2241 [HNOI 2016] 最小公倍数
![]()
2024-09-10 12:43:49
|
|
Pro3922 删除题目 题解首先我们假设两条边 $(u1,v1)$,$(u2,v2)$ 中间未选择断边,则我们可以考虑 DP,设 $f_i$ 表示 必须选 $(fa_i,i)$ 这条边时在其子树内走可以得到的最大贡献,则任意一点 $v$ 在其子树内,则有转移方程 $f_i = \max\limits_{v \in son(i)} f_v + size_v \times (size_u - size_v)$,这东西可以用 李炒熟 维护,对于树形结构可以用 李超树合并 解决子树问题。
但是这显然没完,上述所求的只是在一条链 从子树到祖先 上的路径,然后我们考虑在某个点合并两条链,假设合并两点 $u,v$,则需要再减去重复的贡献 $size_u \times size_v$,所以我们求得答案即为 $f_u + f_v - size_u \times size_v$ 的最大值,显然也可以用 李焯书,然后考虑如何合并,显然可以用 淀粉质,复杂度是 $\mathcal{O}(n\log^2{n})$ 的,但巨大长代码。
知周所众,dsu on tree 是可以代替一些淀粉质的,所以我们考虑用 dsu on tree,考虑每个点 $x$,保存其 重儿子 的李超树,其余节点暴力查询答案,然后进行 李焯书贺兵 即可,复杂度也是 $\mathcal{O}(n\log^2{n})$,但较好写,常数也小。
题目3922 删除题目
AAAAAAAAAAAAAAAAAAAA
![]()
2024-09-05 22:00:36
|
|
首先我们考虑如何求每个点的贡献,可以发现只有最后一次经过某点的时间是有用的,我们可以考虑 最少失去的法力值,设其为 $w$ ,则答案即为 $s \times \sum m - w$,$n$ 较小,考虑状压 DP,因为询问规定了最终点,所以一维是不行的,设 $f_{i,j}$ 表示已经最后一次经过状态 $i$ 中的点,且当前在 $j$ 位置的最小答案,则有状态转移方程: $$f_{i,j} = \min {f_{la,k} + d_{k,j} \times s_{la}}$$
其中 $d_{i,j}$ 表示 $i$ 到 $j$ 的最短路,$s_{i}$ 表示状态 $i$ 中所有节点的 $m$ 和。
然后对于答案,即为 $ans = \underline{s_{i}}_k \times \underline{s}_x + (\underline{-f_{i,j}}_b)$,显然可以 李焯书 解决。
复杂度 $\mathcal{O}(2^nn^2 + 2^nn\log{V} + q\log{V})$,当然也可以维护凸包,但是瓶颈不在这,复杂度差不多。
题目3873 [USACO23 Jan Platinum] Mana Collection
AAAAAAAAAAAAAAAAAAAAAAAA
![]()
2024-09-02 16:46:36
|
|
求 $\sum_{i=1}^{n} \phi(i^2)$ 基本上是裸的杜教筛 一个关于 $\phi$ 的性质:$$\phi(ij) = \frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}$$ 证明:该式本质上是容斥,$\phi$ 的原式子是,当 $n = {p_1}^{c_1}\times {p_2}^{c_2} \times ··· \times {p_m}^{c_k}$ $\phi(n) = n \times \prod_{i=1}^{m} (1 - \frac{1}{p_i})$ 这里式子就表示为先把 $i$ 和 $j$ 的质因数乘上在除去 $i,j$ 的共同质因数,即 $\phi(gcd(i,j))$,最后再消掉 $gcd(i,j)$ 即可得到该式。 然后开始推式子: $$ \sum_{i=1}^{n} \phi(i^2) = \sum_{i=1}^{n} i \times \phi(i) $$ 不难发现该式等于 $\phi \cdot id$ $$ (\phi \cdot id) \ast id = \sum_{d\mid n} d * \phi(d) * \frac{n}{d} = n \times \sum_{d\mid n} \phi(d) = id^2$$ 我们设 $f(n) = n \times \phi(n),S(n) = \sum_{i=1}^{n} f(i)$ ,这里的 $id$ 与 $id^2$ 的前缀和都比较好求。 运用杜教筛公式可得: $$ S(n) = \sum_{i=1}^{n}i^2 - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$ $$ = \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$ 线性筛出前 $n^{\frac{2}{3}}$ 项,整除分块即可
题目3352 平方前缀和
AAAAA
![]()
2024-04-06 15:38:46
|
|
Pro2976 偷笔记 题解挺好的递推+恶心的矩阵快速幂题 题面:有一个n行m列的棋盘,在当前位置可以瞬移,每次可向右瞬移奇数列,且瞬移到本行或相邻行,并且不能瞬移出棋盘,问从$(1,1)至(n,m)$的总方案数 首先考虑递推,设$f(i,j)$为投当前在第i行第j列的方案数,因为每次可以向右瞬移,所以$f(i,j)$可以由上一列,上上上一列...推出来,且可以由上一行和下一行推出 则递推转移方程式为$f(i,j) = \sum_{k=j-w,w=1,w+=2}^j f(i,k)+f(i-1,k)+f(i+1,k)$ 这样直接枚举是$O(nm^2)$的复杂度,肯定是不行的,那我们继续考虑 我们设$g(i,j) = \sum_{k=j-w,w=1,w+=2}^j f(i,k) = g(i,j-2) + f(i,j-1)$ 则方程式转为$f(i,j) = g(i-1,j) + g(i,j) + g(i+1,j) = g(i-1,j-2) + f(i-1,j-1) + g(i,j-2) + f(i,j-1) + g(i+1,j-2) + f(i+1,j-1)$ 我们在维护$f$的同时维护$g$则时间复杂度会降到$O(nm)$ 一看数据$10^9$,再次拿出我们的dz,一眼鉴定为矩阵快速幂 然后就开始我们快(恶)乐(心)的推转移矩阵的时候: 根据转移方程我们可以分成两种情况,即上一列的方案和上上一列的方案,因为上上一列的方案数在推下一列的方案数时要用到,所以不能去掉,我们都需要记录,所以需要当推到$f(i,j)$时,我们需要$f(i,j-1), g(i,j-1), g(i,j-2)$把这三列归为一列,$1至n$为$f(i,j-1)$,$n+1至2n$为$g(i,j-1)$,$2n+1至3n$为$g(i,j-2)$最后该矩阵的长度为$3n$最大为150,则我们转移矩阵大小为$3n * 3n$ 先看应该怎样转移 $$\begin{bmatrix}f(1,j-1) & f(2,j-1) & ... & f(n,j-1) & g(1,j-1) & g(2,j-1) & ... & g(n,j-1) & g(1,j-2) & g(2,j-2) & ... & g(n,j-2) \\\end{bmatrix}$$ 应该转移为 $$\begin{bmatrix}f(1,j) & f(2,j) & ... & f(n,j) & g(1,j) & g(2,j) & ... & g(n,j) & g(1,j-1) & g(2,j-1) & ... & g(n,j-1) \\\end{bmatrix}$$ 所以根据递推转移方程考虑转移矩阵,则可推出矩阵为: 设转移矩阵为$c(i,j)$ 首先先看f的矩阵:根据递推方程 当$f(i,j)$时 只需将$c(i-1,i),c(i,i),c(i+1,i)$设为1,才加上$g$即将$c(2*n+i-1,i),c(2*n+i,i),c(2*n+i+1,i)$再设为1就可以了 再考虑$g(i,j)$ 由递推方程式得 应当将$c(i,i+n),c(i+2*n,i+n)$置为1即可 最后看$g(i,j-1)$ 在转移前已经出现,不需要推,所以只要将$c(i+n,i+2*n)$置为1即可 (因为矩阵实在太大画不下,只好描述一下) Oo最后开始愉悦的矩阵快速幂时刻oO 复杂度为$O(150^3*log(1e9))$,大约为$1e8$所以跑的飞慢qwq 二维递推实在痛苦┭┮﹏┭┮
题目2976 偷笔记
AAAAAAAAAA
![]()
2023-11-21 20:41:53
|