无

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

树专题 我咋还没做完

保序回归问题

无

无

无

无

无

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

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

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$ 个点无法被选，因此一定存在满足题意的独立集。
• 备注：发现最大环长度和独立集点数的关系是比较巧妙的。同时复习了求无向图最大环的方法。

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