2020-2021:teams:hotpot:200725-200731

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:200725-200731 [2020/07/31 15:43]
lotk
+++ 2020-2021:teams:hotpot:200725-200731 [2020/07/31 16:23] (当前版本)
misakatao 更新
@@ 行 15: / 行 15: @@
 =====比赛=====
-.7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:4/5/7'' ''rank:2746''
+.7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:3/4/7'' ''rank:2331''
 =====题目=====
+本周无
 ======陶吟翔======
@@ 行 48: / 行 50: @@
 .7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:4/6/7'' ''rank:993/24680''
+.7.30 [[codeforces660div2|Codeforces Round #660]] ''prob:4/4/5'' ''rank:279''
 =====题目=====
@@ 行 55: / 行 59: @@
 ======本周推荐======
-林星涵：
+林星涵：[[https://codeforces.com/contest/1389/problem/D|Educational Codeforces Round #92 D]]
-题目大意：
+题目大意：分别给出两种 $n$ 个区间都为 $[l1,r1],[l2,r2]$ , 一次操作可以将一个区间左右端点移动1，问最少操作多少次能够使第一类和第二类的重合部分长度之和达到 $k$.
-数据范围：
+数据范围：$1 \le n \le 2e5 ,1 \le k\le 1e9 ,1\le l \le r \le 1e9$
-解题思路：
+解题思路：由题意，由于初始区间相同，我们可以根据初始区间的情况进行分类讨论（包含，相交，不相交），再根据所得到的条件分类进行贪心处理。
-推荐理由：
+推荐理由：分类的贪心题，需要较为清晰的思路和分类。
 陶吟翔：
-题目大意：
+题目大意：给出一个$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.1596181389.txt.gz · 最后更改: 2020/07/31 15:43 由 lotk