假设我们定义一个有根树 $T$ 上一个节点为 $u$，其中其儿子为 $v$，则 $H(v) = f()$，则 $H(T) = H(root)$ 其中 $f$ 通常为 $f(v) = hash(sort())$，例如 $f(v) = \sum_^k v_i$ 自然溢出。 假设...

1015 字 丨 3.4分钟

引 给你两棵树 $A,B$ 并且告诉你 $A$ 的最远点对为 $(a,b)$，$B$ 的最远点对为 $(c,d)$，假设此时用一条边将树 $A,B$ 相连，形成了一颗新的树，那么此时证明新的树的最远点对 $(e,f)$ 满足 $e,f \in $。 我们不难想到进行分类讨论...

4720 字 丨 15.7分钟

T1 设 $f_$ 为 $A$ 序列最后一个为 $i$，$B$ 序列最后一个为 $j$，所得到的 $|A|+|B|$ 最大值。 直接转移即可。 T2 注意到翻转 $l,r$ 时只有 $l,r$ 这个区间内的改变会有贡献。 此时假设 $g_i$ 为 $\sum_^i \max...

453 字 丨 1.5分钟

T1 题目描述 这是 SA 酱 (angel ver.) 的卡面介绍. SA 酱现在有一个长 $n$ 的序列 $a_1,\dots,a_n$，初始时候 $a_i=i$. 定义序列的价值为 $(a_1\oplus 1)+(a_2\oplus 2)+\dots+(a_n\opl...

1994 字 丨 6.6分钟

问题引入 如果我们需要一种算法，使其可以将一个字符串的所有子序列表示为一个 DAG（即有向无环图），我们该如何构建？ 构建 钦定 $n$ 为字符串的长度，$\Sigma$ 为字符集，$S$ 为字符串，且 $S$ 只会包含小写字母。 我们定义 $nxt_ (i \leq ...

3578 字 丨 11.9分钟