2020-2021:teams:i_dont_know_png:week_summary_12
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_12 [2020/07/23 10:42] nikkukun |
2020-2021:teams:i_dont_know_png:week_summary_12 [2020/07/31 15:42] (当前版本) nikkukun edit title hierarchy |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| + | ^ 比赛时间 ^ 比赛名称 ^ | ||
| + | | 2020.07.18 | [[multi2020-nowcoder-3 | 2020 Nowcoder Multi-University Training Contest 3]] | | ||
| + | | 2020.07.20 | [[multi2020-nowcoder-4 | 2020 Nowcoder Multi-University Training Contest 4]] | | ||
| + | | 2020.07.20 | [[SaratovSU2015 | 2015-2016 Petrozavodsk Winter Camp, Saratov SU Contest]] | | ||
| - | ===== 团队会议 ===== | ||
| + | ===== 团队会议 ===== | ||
| + | 无 | ||
| 行 13: | 行 18: | ||
| ===== 个人训练 - nikkukun ===== | ===== 个人训练 - nikkukun ===== | ||
| + | |||
| + | 本周在刷一些 1900-2200 的题目提升码力。 | ||
| + | |||
| + | ==== 专题 ==== | ||
| + | |||
| + | [[https://vjudge.net/contest/380720#overview | 树专题]] <del>我咋还没做完</del> | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === 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 ^ | ||
| 行 26: | 行 37: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| - | === 杂项 === | + | [[.:nikkukun:isotonic_regression | 保序回归问题]] |
| - | ''std::vector/map/set/deque::swap'' 可以常数交换两个容器（避免启发式合并时换来换去）。 | ||
| - | ''std::list::splice'' 可以常数合并两个 list。不能用 ''std::list::merge''，这是类似链表归并的东西，要重载小于号。 | ||
| - | === 可并堆 === | ||
| - | pb_ds 中的可并堆： | ||
| - | <code:c++> | ||
| - | #include <ext/pb_ds/priority_queue.hpp> | ||
| - | using namespace __gnu_pbds; | ||
| - | __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> q; // 大根堆 | ||
| - | </code> | ||
| - | 常用 pairing_heap_tag 和 binomial_heap_tag，但由于 pairing_heap_tag 的合并是 $O(1)$ 而后者是 $O(\log n)$ 的，实测是前者快一点。 | + | ===== 个人训练 - qxforever ===== |
| - | 这两个东西的其他操作都是 $O(\log n)$ 的。 | ||
| + | ==== 专题 ==== | ||
| - | === 维护技巧 === | + | 无 |
| - | + | ||
| - | 对有一定偏序关系的集合，可以按偏序关系分成小于、等于、大于三类标记，或者是以此为时间线进行修改。 | + | |
| - | + | ||
| - | 例如，按边权从小到大加边是最常见的一种做法，或者能证明这样的修改量是有限的。另一种例子是，从小到大枚举元素，每次只会让有限个大于标记的元素变为小于，也是一种单调的变化（进而可以用线段树之类的维护）。 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | ==== 本周推荐 ==== | + | |
| - | + | ||
| - | === Petrozavodsk Winter 2020. Day 5. Jagiellonian U Contest D - Clique === | + | |
| - | + | ||
| - | [[https://codeforces.com/gym/102576/problem/D | 题目链接]] | + | |
| - | + | ||
| - | **题意**：一个圆被分为 $10^6$ 份并标号，给 $n \leq 3000$ 段圆上的弧，每段弧都对应了一段连续的标号。尽可能多地选出弧，使得任意选中的两条弧都有至少一个标号相同。 | + | |
| - | + | ||
| - | **题解**：一个比较详细的题解 [[https://www.cnblogs.com/iefnah06/p/13020641.html | 见此]] | + | |
| - | + | ||
| - | **推荐理由**：本题妙的地方在于，它将相交的判定，变成了两个相关量的判定，进而转化为平面上的几何问题，并发现这个问题可以用 DP 解决。 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | ===== 个人训练 - qxforever ===== | + | |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === 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 ^ | ||
| 行 84: | 行 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 ^ | ||
| 行 92: | 行 68: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| - | ==== 本周推荐 ==== | ||
| - | === === | ||
| - | [[|题目链接]] | ||
| + | ===== 个人训练 - Potassium ===== | ||
| + | ==== 专题 ==== | ||
| + | 无 | ||
| - | ===== 个人训练 - Potassium ===== | + | ==== 比赛 ==== |
| + | 无 | ||
| - | ==== 比赛 ==== | + | ==== 学习总结 ==== |
| - | ==== 学习总结 ==== | + | 无 |
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== 本周推荐 ===== | ||
| + | ==== nikkukun ==== | ||
| - | ==== 本周推荐 ==== | + | [[https://codeforces.com/gym/102576/problem/D | Petrozavodsk Winter 2020. Day 5. Jagiellonian U Contest D - Clique]] |
| + | * **题意**：一个圆被分为 $10^6$ 份并标号，给 $n \leq 3000$ 段圆上的弧，每段弧都对应了一段连续的标号。尽可能多地选出弧，使得任意选中的两条弧都有至少一个标号相同。 | ||
| + | * **题解**：一个比较详细的题解 [[https://www.cnblogs.com/iefnah06/p/13020641.html | 见此]]。 | ||
| + | * **备注**：本题妙的地方在于，它将相交的判定，变成了两个相关量的判定，进而转化为平面上的几何问题，并发现这个问题可以用 DP 解决。 | ||
| - | === === | ||
| - | [[|题目链接]] | + | ==== qxforever ==== |
| - | **题意**： | + | CF 1325F |
| - | **题解**： | + | * **题意**：给一个 $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 ==== | ||
| + | ARC 084 D Small Multiple | ||
| + | * **题意**：给定 $n \leq 10^5$，求它的倍数 $kn$ 的最小数位和。 | ||
| + | * **题解**：这个题目可以用最短路解。考虑限制条件即为 $kn \equiv 0 \pmod n$，因此我们只需要找到一个模 $n$ 为 $0$ 的数 $x$，且 $x$ 的数位和最小即可。 | ||
| + | * 假如我们知道了 $x$ 的数位和，则从 $x \rightarrow x+1$ 会让数位和增加 $1$（暂时忽略进位的情况），从 $x \rightarrow 10x$ 不会增加数位和。因此我们可以在模意义下给 $0, 1, \ldots, k-1$ 分别增加边 $(x,\ x+1)$ 与 $(x,\ 10x)$，并设边权分别为 $1$ 和 $0$，跑一个到 $0$ 的最短路即可。这个时候重新考虑进位的情况：虽然过程中增加了一些冗余的边，但是进位会在乘 $10$ 的边上计算，因此实际不会有问题。 | ||
| + | * 初始条件是 $\mathrm{dis}(1) = 1$。 | ||
| + | * **备注**：比较神秘的思维题。 | ||
2020-2021/teams/i_dont_know_png/week_summary_12.1595472167.txt.gz · 最后更改: 2020/07/23 10:42 由 nikkukun
