ABC397赛后总结
Handezheng
·
·
学习·文化课
庆幸打了 unrated，惋惜没有做出E
A
过
B
过
C
过
D
发现直接枚举会爆时间和 long long，先优化精度问题。
发现所求可用立方差公式优化为 (x-y)\cdot(x^2+xy+y^2)=n。
能够得到 (x-y)和(x^2+xy+y^2) 都是 n 的因数，所以直接枚举因数 c，时间 O(\sqrt n)。
$$
\begin{aligned}
c\times((y+c)^2 + y(y+c) + y^2) &= n \\
(y+c)^2 + y(y+c) + y^2 &= \frac n c \\
3y^2 + 3cy &= \frac n c - c^2 \\
y^2 + cy &= \frac{\frac n c - c^2}{3}
\end{aligned}
$$
得到 $y=\frac{-c + \sqrt{c^2+4t}}{2}$。
而又因为 $(x-y)$ 最多是 $\sqrt[3] n$，所以时间复杂度为 $O(\sqrt[3] n)$。
赛时没想到枚举到 $\sqrt[3] n$ 就可以，硬控半小时，最后还是试出来的。
### E
树形DP可做。
发现要么是一条树链，要么是一条树上的路径，而且子树个数不大于2。
若子树个数为1，直接加；子树个数为2，两条链长度加1必为 $K$，转移很巧妙，见[炜哥代码](https://atcoder.jp/contests/abc397/submissions/63800231)。
赛时没做出来，惋惜痛恨之。
### F
类似的题 [CF833B](https://codeforces.com/problemset/problem/833/B)。
线段树优化DP
$$
令f_{i,j} 表示划分成i层，到第j个点的最大价值\\
易得转移方程f_{i,j}=\max_{k=1}^{j-1}{f_{i-1,k}+cnt_{k+1,j}}
$$
因为是max，所以可以考虑线段树维护这个东西，按 $i$ 枚举，每次到新的一层重新建树维护。
而F题就是 $K=3$ 时的结果。
赛时根本没看这道题，预估看了也写不出来。