====== 2020.07.18-2020.07.24 周报 ======


===== 团队训练 =====

^  比赛时间  ^  比赛名称  ^
|  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]]  |


===== 团队会议 =====

无




===== 个人训练 - nikkukun =====

本周在刷一些 1900-2200 的题目提升码力。

==== 专题 ====

[[https://vjudge.net/contest/380720#overview | 树专题]] <del>我咋还没做完</del>

==== 比赛 ====


**2020.07.21 Codeforces Round #658 (Div. 1)**

^  题目  ^  A1  ^  A2  ^  B  ^  C  ^  D  ^  E  ^
|  通过  |  √  |  √  |  √  |     |     |     |
|  补题  |     |     |     |     |     |     |


==== 学习总结 ====

[[.:nikkukun:isotonic_regression | 保序回归问题]]






===== 个人训练 - qxforever =====


==== 专题 ====

无


==== 比赛 ====

**2020.07.21 Codeforces Round #403 (Div. 1)**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √  |     |     |     |
|  补题  |     |     |     |     |     |     |

**2020.07.21 Codeforces Round #658 (Div. 1)**

^  题目  ^  A1  ^  A2  ^  B  ^  C  ^  D  ^  E  ^
|  通过  |  √  |  √  |  √  |     |     |     |
|  补题  |     |     |     |  √  |     |     |

==== 学习总结 ====

无







===== 个人训练 - 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$。
  * **备注**：比较神秘的思维题。