2024/04/29(#36)：世界像个动物乐园，那么那么大超级乐园

这里什么都有！

VP Petrozavodsk Summer 2019. Day 2. 300iq Contest 2, Grand Prix of Kazan。

这下真的菜就多练了

B. Bitwise Xor

建出 Trie 树可以发现 DFS 序相邻的数能达到最小值，因此直接 Trie + DP 即可。

I. Interactive Vertex

直接点分治下去，每次需要二分，询问次数是 $O(\log^2 n)$ 的，每次需要排除至少一半的大小，因此二分时候带个权值即可。

G. Grammarly

正常答案是 $2^n-1$，对于一个连续字符的状态 $[l,r]$，能够到达它的方案数是 $\binom{n-len}{l-1}$，其现在的方案数是 $len$。然后对于每个能够到达的连续字符状态的前缀后缀的答案也要减去。

E. Easy Win

线性代数，滚。

我只能相信他不可能考拟阵。

要学的（可能不是很重要）：

• 线性基相关应用
• 行列式
• LGV，BEST，矩阵树

F. Fast Spanning Tree

之前听说过减半警报器的名字，没想到这次真的碰到了。

将需要的权值各自分一半，然后接着跑即可。