2020-2021:teams:hotpot:200725-200731
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200725-200731 [2020/07/31 12:11] misakatao 更新 |
2020-2021:teams:hotpot:200725-200731 [2020/07/31 16:23] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:3/4/7'' ''rank:2331'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 本周无 | ||
| ======陶吟翔====== | ======陶吟翔====== | ||
| 行 26: | 行 30: | ||
| 2020.7.24 [[topcodersrm788div2|Topcoder SRM 788 DIV2]] ''prob:3/3/3'' （因为打的时候上周周报已经交了所以算在这周） | 2020.7.24 [[topcodersrm788div2|Topcoder SRM 788 DIV2]] ''prob:3/3/3'' （因为打的时候上周周报已经交了所以算在这周） | ||
| + | |||
| + | 2020.7.25 [[m-solutionsprogrammingcontest2020|M-SOLUTIONS Programming Contest 2020]] ''prob:5/5/6'' ''rank:282'' | ||
| + | |||
| + | 2020.7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:4/5/7'' ''rank:744'' | ||
| + | |||
| + | 2020.7.30 [[codeforces660div2|Codeforces Round #660]] ''prob:4/4/5'' ''rank:261'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 本周无 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| 行 36: | 行 48: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.7.29 [[codeforcesER92|Educational Codeforces Round #92]] ''prob:4/6/7'' ''rank:993/24680'' | ||
| + | |||
| + | 2020.7.30 [[codeforces660div2|Codeforces Round #660]] ''prob:4/4/5'' ''rank:279'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 本周无 | ||
| ======本周推荐====== | ======本周推荐====== | ||
| - | 林星涵： | + | 林星涵：[[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算法，但是没有学习过这个算法的做题者依然可以通过分析得到解决方法，即考察了做题者的知识面又考察了做题者随机应变设计算法的能力 |
| 郭衍培： | 郭衍培： | ||
| 题目大意： | 题目大意： | ||
| + | |||
| + | 给定n个闭区间，每个区间有一个颜色t。从中取若干区间，要求任意两个颜色不同的区间没有交集为空。问最多取几个区间 | ||
| 数据范围： | 数据范围： | ||
| + | |||
| + | $1\le n \le 2\cdot 10^5$,$1\le l_i \le r_i \le 10^9$,$t_i\in \{1,2\}$ | ||
| 解题思路： | 解题思路： | ||
| + | |||
| + | 每个区间建一个点。若两个区间不能放在一起，则连上边。本题等价于求这个二分图的最小割（去掉若干个点，剩余点两两不相连），也就等价于求这个二分图的最大匹配。 | ||
| + | |||
| + | 这个最大匹配我们可以贪心。首先按区间左端点排序。每次放入一个新点，删去原图中所有右端小于新点左端的点。找到与新点颜色不同的点中，右端最小的，和其进行匹配。 | ||
| + | |||
| + | 设这个最大匹配是m，最终答案为n-m | ||
| 推荐理由： | 推荐理由： | ||
| + | |||
| + | 方法巧妙，也很好写。 | ||
2020-2021/teams/hotpot/200725-200731.1596168684.txt.gz · 最后更改: 2020/07/31 12:11 由 misakatao
