CF 快乐板刷之路

imily's notebook

2021-07-09

$CF1396E-Distance Matching$

这种极易停止撕烤的题先考虑有无解。即求答案范围。

$dist(x, y) = dis_x + dis_y - 2 dis_{lca(x, y)}$

最小化 lca $dis$ 之和，尽量在浅的点配完

！根据某经典模型，选重心可以配完并且 lca 都是重心。同理求得 $minans$。

$maxans = \sum dis_i = \sum [i \neq root] sz_i$ $minans = \sum [i \neq root] (sz_i \mod 2)$

$maxans - k$ 显然必须是 $2$ 的倍数。否则设 $rest = (maxans - k) / 2$，显然可以通过不断选大小最大的子树的一对点配对使得 $rest$ 变小。~~模拟？😅~~

可以将某些非叶子节点变成 lca。具体来说：

$rest \geq$ 大小最大的子树深度 $d$ 时，选该子树最深的那对兄弟或父亲，$rest -= d - 1$ (I)
否则令深度 $rest$ 的点为 lca (II)

细节：

set 维护重心所有子树的大小和 id，方便找最大子树
对每个子树开一个 set 维护子树中点的深度和 id，方便找最深点
只有一次是 II 情况，其余都是 I，I 显然每次删的都是两个叶子的父亲或一个叶子和它的父亲，所以点匹配掉要记得将父亲度数减一（还要从父亲的叶子集合里删掉，但是想要快速删除就要多个 log，还是懒惰删除更香一点，即遇见时删除），父亲成为叶子就把父亲从备选深度集合里踢掉。

$Code$

$CF1322E-Median Mountain Range$

中位数问题，想到「01 序列」基本这题就只剩代码难度了。

我们把长度 $> 1$ 的 0 和 1 称为 0 段和 1 段，0、1 交错出现的称为 01 段。
显然 0 段和 1 段是稳定的，
01 交错出现部分每次操作会两边各缩进去一个单位。

拓展，$\leq x$ 为 1，$> x$ 为 0。某位取值为 $a$，当且仅当 $x = a$ 时该位置的终态改变。

从小到大枚举 $x$。操作次数 $=$ 所有 $x$ 的操作次数 $max$，因为实际操作序列肯定存在最后一步，当 $x =$ 最后一步的中位数时取到 $max$。

细节：

每次 0 -> 1 可能会让 0 段和 01 段变为 01 段和 1 段。每次操作只会至多出现一个 01 段需要赋值。

并查集维护同色块，set 维护同色对的位置（这俩方便确定 01 交错段的端点坐标）
set 维护 0 的位置，防止对 01 交错段中的 0 重复赋值（赋值指 $ans = x$）。

$Code$

$CF1481F-AB Tree$

考虑枚举答案。设最大深度为 $l$，那么答案下界为 $l$，当且仅当每个深度颜色相同。

背包？物品种类 $O(\sqrt{n})$ 级别，也就是说 $O(n \sqrt{n})$ 的复杂度即可判断答案能否为 $l$。$dp[x, i]$ 表示前 $x$ 种物品填了 $i$ 个 a，bitset + 多重背包

然后呢？

官解告诉我们上界为 $l + 1$。证明见如下构造过程，有点脑筋急转弯的感jio：

将点分为叶子节点和非叶子节点，非叶子节点个数 $\leq \frac{n}{2}$ 个，每层非叶子节点必然可以同色，考虑从上往下填色，每层的非叶子节点先填同一种颜色，然后同层的叶子节点尽量填该层非叶子节点的颜色，若填完了就填另一种。

$Code$

$CF827F-Dirty Arkady’s Kitchen$

策略是反复横跳。设「最小时刻」的 dp 状态是不对的，因为如果来的边 ban 掉，又没有邻边存在，就会挂。

按出现时间从小到大加边，堆维护，$f[x, 0/1]$ 表示在偶/奇时刻到达 $x$ 点的最大时刻，那么加入的边出现时间只要 $\leq f[x, 0/1]$ 就可以拓展，否则 $> f[x, 0/1]$ 就先放在 $x$ 的 vector 里，等到什么时候 $f[x, 0/1]$ 更新了才拓展（更新 $f[x, 0/1]$ 一定是之后的边的 $r$，一定大于当前边的 $l$，所以一定可以拓展）。因为边有序，vector 也有序。显然你不用考虑删边了。

这样一条边最多被考虑两次，复杂度 $O(nlogn)$。

$Code$

$CF1550D-Excellent Arrays$

卡点很奇怪的一道题（？

设 $k_i = a_i - i$，那么 $k_i = -k_j$ 的对贡献 $1$，也就是说按 $|k_i|$ 划分，每个部分内部贡献的和最大

~~然后我到这儿就卡住了~~

显然可以划分为一个集合，其中一半 $+k$，一半 $-k$，因此 $F(a) = (n/2)^2$

不同 $k$ 的贡献计算方式不同。

$k \leq min(1 - l, r - n)$：偶长度序列答案为 $\binom{n}{n/2}$，奇长度序列答案为 $\binom{n}{n/2} + \binom{n}{(n/2) + 1}$，就考虑选了哪些为 $+k$
$k > min(1 - l, r - n)$：设 $lf = max(1, l + k) + 1$, $rg = min(n, r - k) - 1$
$i \in [1, lf)$ 只能选 $+k$, $i \in (rg, n]$ 只能选 $-k$。稍微推一下得到，偶长度序列答案为 $\binom{rg - lf + 1}{(n/2) - lf + 1}$, 奇长度序列答案为 $\binom{rg - lf + 1}{(n/2) - lf + 1} + \binom{rg - lf + 1}{(n/2) + 1 - lf + 1}$

这部分复杂度是合法 $k$ 的个数，是多少呢？$k$ 每 $+1$，$lf++$、$rg—$，直到 $rg - lf + 1 \leq 0$，一共是 $O(n)$ 个 $k$。

$Code$