无

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

树专题 我咋还没做完

保序回归问题

无

无

无

无

无

Petrozavodsk Winter 2020. Day 5. Jagiellonian U Contest D - Clique

• 题意：一个圆被分为 $10^6$ 份并标号，给 $n \leq 3000$ 段圆上的弧，每段弧都对应了一段连续的标号。尽可能多地选出弧，使得任意选中的两条弧都有至少一个标号相同。
• 题解：一个比较详细的题解 见此。
• 备注：本题妙的地方在于，它将相交的判定，变成了两个相关量的判定，进而转化为平面上的几何问题，并发现这个问题可以用 DP 解决。

CF GYM - 102302I

• 题意：动态随机插入维护上凸包。
• 题解：直接维护就行。维护的时候需要注意的事情：
  • 按 $x$ 递增，$y$ 递减的方式排序。
  • 先不插入点，考虑将插入点左右的位置，用叉积判断是不是需要删除。注意删除之后迭代器可能会发生变化，要重新找一次插入点。
  • 判断在凸包内外时，比较插入位置前后的连线与插入点的关系，再决定要不要插入。
  • （只适用于本题）需要额外考察凸包两端点的斜率。
• 备注：写起来需要注意很多细节的题目，练一练能够提升对维护过程的理解。

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$。
• 备注：比较神秘的思维题。