2020-2021:teams:i_dont_know_png:week_summary_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_12 [2020/07/24 17:33] 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 ^ | ||
| 行 101: | 行 101: | ||
| [[https://codeforces.com/gym/102576/problem/D | Petrozavodsk Winter 2020. Day 5. Jagiellonian U Contest D - Clique]] | [[https://codeforces.com/gym/102576/problem/D | Petrozavodsk Winter 2020. Day 5. Jagiellonian U Contest D - Clique]] | ||
| - | * 题意：一个圆被分为 $10^6$ 份并标号，给 $n \leq 3000$ 段圆上的弧，每段弧都对应了一段连续的标号。尽可能多地选出弧，使得任意选中的两条弧都有至少一个标号相同。 | + | * **题意**：一个圆被分为 $10^6$ 份并标号，给 $n \leq 3000$ 段圆上的弧，每段弧都对应了一段连续的标号。尽可能多地选出弧，使得任意选中的两条弧都有至少一个标号相同。 |
| - | * 题解：一个比较详细的题解 [[https://www.cnblogs.com/iefnah06/p/13020641.html | 见此]]。 | + | * **题解**：一个比较详细的题解 [[https://www.cnblogs.com/iefnah06/p/13020641.html | 见此]]。 |
| - | * 备注：本题妙的地方在于，它将相交的判定，变成了两个相关量的判定，进而转化为平面上的几何问题，并发现这个问题可以用 DP 解决。 | + | * **备注**：本题妙的地方在于，它将相交的判定，变成了两个相关量的判定，进而转化为平面上的几何问题，并发现这个问题可以用 DP 解决。 |
| ==== qxforever ==== | ==== 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 ==== | ==== 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.1595583187.txt.gz · 最后更改: 2020/07/24 17:33 由 nikkukun
