CYEZ 模拟赛 5

难难比赛。

A 堆

记 $f_i$ 表示 $i$ 时的答案，$L,R$ 分别为左右子树。把 $f$ 视为相对大小，易得下式：

$$f_i=\left(\genfrac{}{}{0ex}{}{i-1}{L}\right)f_L{f}_R$$

$L,R$ 中一定有一颗满二叉树。可以 $O(1)$ 得到均为满二叉树时的上下界，根据实际大小与上下界的偏离程度可以得到具体的 $L,R$ 大小。

组合数计算次数为 $O(\log n)$，考虑分段打表处理组合数。记 $B$ 为块长，类似分块的思想，整块打表预处理，散块暴力算。又因为 $L,R$ 中有一颗为满二叉树，打表预处理出满二叉树的答案。

至此，时间复杂度 $O(B\log n)$，空间复杂度 $O(\frac{n}{B})$。

代码

B 密文

将区间视为边，转换为在这张完全图上做 MST。

若存在 $a_u=a_v$，$u,v$ 边一定连且对答案无影响。因此只考虑点权互不相同的情况。

在 0-1 Trie 上考察 Kruskal 的过程。每次取异或和最小的两点，视为取深度最深的 lca。而在点权互不相同的情况下，有两个儿子的点有 $n-1$ 个，恰好对应 $n-1$ 条边。

代码

C 树

总结

遇到难难比赛，打部分分是合理的。

预计 $60+40+0$，实际 $60+40+0$。A 场上似乎想到了分块的思想，但没有尝试过并没有加以实现。B 写了 $n^2$ 的 MST。C 为啥不打暴力？？