2020-2021:teams:i_dont_know_png:week_summary_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_12 [2020/07/24 17:40] nikkukun |
2020-2021:teams:i_dont_know_png:week_summary_12 [2020/07/31 15:42] (当前版本) nikkukun edit title hierarchy |
||
|---|---|---|---|
| 行 28: | 行 28: | ||
| - | === 2020.07.21 Codeforces Round #658 (Div. 1) === | + | **2020.07.21 Codeforces Round #658 (Div. 1)** |
| ^ 题目 ^ A1 ^ A2 ^ B ^ C ^ D ^ E ^ | ^ 题目 ^ A1 ^ A2 ^ B ^ C ^ D ^ E ^ | ||
| 行 54: | 行 54: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === 2020.07.21 Codeforces Round #403 (Div. 1) === | + | **2020.07.21 Codeforces Round #403 (Div. 1)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| 行 60: | 行 60: | ||
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| - | === 2020.07.21 Codeforces Round #658 (Div. 1) === | + | **2020.07.21 Codeforces Round #658 (Div. 1)** |
| ^ 题目 ^ A1 ^ A2 ^ B ^ C ^ D ^ E ^ | ^ 题目 ^ A1 ^ A2 ^ B ^ C ^ D ^ E ^ | ||
| 行 108: | 行 108: | ||
| ==== qxforever ==== | ==== qxforever ==== | ||
| - | CF GYM - 102302I | + | CF 1325F |
| - | + | ||
| - | * **题意**：动态随机插入维护上凸包。 | + | |
| - | * **题解**：直接维护就行。维护的时候需要注意的事情： | + | |
| - | * 按 $x$ 递增，$y$ 递减的方式排序。 | + | |
| - | * 先不插入点，考虑将插入点左右的位置，用叉积判断是不是需要删除。注意删除之后迭代器可能会发生变化，要重新找一次插入点。 | + | |
| - | * 判断在凸包内外时，比较插入位置前后的连线与插入点的关系，再决定要不要插入。 | + | |
| - | * （只适用于本题）需要额外考察凸包两端点的斜率。 | + | |
| - | * **备注**：写起来需要注意很多细节的题目，练一练能够提升对维护过程的理解。 | + | |
| - | + | ||
| + | * **题意**：给一个 $n$ 个点的无向图，求一个大于 $\lceil \sqrt n\rceil$ 的环或找出 $\lceil \sqrt n\rceil$ 个点的独立集。 | ||
| + | * **题解**： | ||
| + | * 环：可以通过 DFS 树找最大环。对于非树边 $(a,b)$ ，存在大小为 $dep_b-dep_a+1$ 的环。 | ||
| + | * 独立集：如果不存在 $\lceil \sqrt n\rceil$ 的环，那么每个点最多有 $\lceil \sqrt n\rceil -2 $ 的条非树边。即我们每选一个点，最坏会导致 $\lceil \sqrt n \rceil -1$ 个点无法被选，因此一定存在满足题意的独立集。 | ||
| + | * **备注**：发现最大环长度和独立集点数的关系是比较巧妙的。同时复习了求无向图最大环的方法。 | ||
| ==== Potassium ==== | ==== Potassium ==== | ||
2020-2021/teams/i_dont_know_png/week_summary_12.1595583600.txt.gz · 最后更改: 2020/07/24 17:40 由 nikkukun
