2020-2021:teams:hotpot:200725-200731
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:200725-200731 [2020/07/31 15:55] lotk |
2020-2021:teams:hotpot:200725-200731 [2020/07/31 16:23] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 71: | 行 71: | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：给出一个$n$个点的树，每条边有边权，可以在任意两点之间加边，不过任何时刻都要满足所有环上边权的异或和为零且整个图联通，最小化所有边的权值之和 |
| - | 数据范围： | + | 数据范围：$2 \le n \le 10^5$，边权$w < 2^{30}$ |
| - | 解题思路： | + | 解题思路：我们按照每个点到根路径上的疑惑和$a_i$给每个点赋一个点权，然后经过分析可以发现在任意两点之间连一条边边权就是这两个点的点权的异或和，问题变成了给出$n$个点权，求最小异或生成树。这个问题可以用Boruvka算法解决。Boruvka算法本质上是每次找到两个连通块之间最小的边，然后把两个连通块合并，在解决最小异或生成树的时候，每次找到两个连通块间最小的边的时间是$O(n \log n)$，合并最多进行$O(\log n)$次，因此复杂度为$O(n \log^2 n)$。我们在比赛的时候的解法类似，首先把所有的点权排序，按照最高位分类，最高位是0的和最高位是1的肯定作为两个连通块并且中间最多连一条边，我们用$O(n \log n)$的时间找到它们中间连的边的最小值加入答案，然后两侧分治，这个过程最多进行$O(log n)$次，因此算法复杂度为$O(n \log^2 n)$ |
| - | 推荐理由： | + | 推荐理由：题目的模型可以较为简单地转化为最小异或生成树，首先考察了做题者的问题转化能力。其次，这道题虽然正解是Boruvka算法，但是没有学习过这个算法的做题者依然可以通过分析得到解决方法，即考察了做题者的知识面又考察了做题者随机应变设计算法的能力 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200725-200731.1596182147.txt.gz · 最后更改: 2020/07/31 15:55 由 lotk
