2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10 [2020/08/10 22:52] qxforever [qxforever] |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-10 [2020/08/11 16:42] (当前版本) nikkukun add E & J. |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== E - Game ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | 水题不表。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== J - Identical Tree ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给两个 $n \leq 500$ 结点的带标号有根树 $T_1, T_2$，求最少要将第一棵树中多少个标号改变，才能和第二棵树相同。保证两棵树同构。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 记 $f(i, j)$ 为将 $T_1$ 的子树 $i$ 和 $T_2$ 的子树 $j$ 匹配最小需要修改的点数，那么每次只需要对 $i$ 和 $j$ 的所有儿子节点找一个完美匹配，使得 $\sum _{u, v \text{ are matched}} f(u, v)$ 最小，这个用 KM 做就行。注意匹配只在两个子树同构的情况下才会进行，可以用树哈希判断一下。 | ||
| + | |||
| + | 我也不知道复杂度的正确性证明……但是菊花图上 $O(n^3)$，完全 $\sqrt n$ 叉树上 $O(n^{2.5})$，完全二叉树上 $O(n^2)$，实际确实能过。 | ||
| 行 25: | 行 53: | ||
| 最近软工小学期开始了导致昨天睡太晚，中午一睁眼 12:15 ... 前半场人一直都晕晕的，前期丢了很多进度 + 整场写挂了很多发。深刻反省！ | 最近软工小学期开始了导致昨天睡太晚，中午一睁眼 12:15 ... 前半场人一直都晕晕的，前期丢了很多进度 + 整场写挂了很多发。深刻反省！ | ||
| + | |||
| ==== Potassium ==== | ==== Potassium ==== | ||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-10.1597071179.txt.gz · 最后更改: 2020/08/10 22:52 由 qxforever
