2020-2021:teams:i_dont_know_png:multi2020-nowcoder-4

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-4 [2020/07/21 07:53]
qxforever [解题思路]
+++ 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-4 [2020/08/07 09:30] (当前版本)
potassium D
@@ 行 2: / 行 2: @@
 [[https://ac.nowcoder.com/acm/contest/5669 | 比赛链接]]
+===== A - Ancient Distance =====
+Upsolved by nikkukun.
+==== 题目描述 ====
+给一个 $n$ 个点，根为 $1$ 的树，你可以选任意 $k$ 个点的点集 $S$，并定义 $f_S(u)$ 为 $u$ 到其最近的 $S$ 中的祖先（可以是自己）的距离。
+对 $k = 1, 2, \ldots, n$，计算
+$$
+\min_{|S| = k} \sum_{i=1}^n f_S(i)
+$$
+==== 解题思路 ====
+反过来考虑距离的上限 $\mathrm{len}$，则随着上限的减小，需要点的个数是非降的。当距离上限确定时，一种最优的方案是每次取树中未被染色的、深度最深的节点，并将其 $\mathrm{len}$ 级祖先加入 $S$，对该祖先的子树染色，如此操作直至整棵树都染色完毕。染色的过程可以线段树维护 DFS 序。
+对确定的 $\mathrm{len}$，单次取出一个祖先会让至少 $\mathrm{len}$ 个点被染色，因此操作次数是 $O \left(\dfrac n{\mathrm{len}} \right)$ 的。对 $\mathrm{len} = 1, 2, \ldots, n$ 依次计算答案，总时间复杂度为
+$$
+O \left( \sum _{\mathrm{len}=1}^n \dfrac n{\mathrm{len}} \cdot \log n \right)
+= O(n \log ^2 n)
+$$
@@ 行 30: / 行 62: @@
 注意到这样的串可以用一个十元组唯一表示，因此可以枚举子串的开头结尾字符分别是十元组的哪两个位置，并按照这两个位置中间的子元组进行分类，计算出对一段中间固定的子元组，向左右添加字符可以构成什么串。这个问题相当于求二维平面上一些点向左下构成的矩形中，一共覆盖了多少个整点。
-这里在比赛时写得非常混乱，是因为没有处理好边界重复的情况。如果设定好加在两端的字符都至少有一个，则这样子并不会出现重复（需要额外加上开头结尾是同一段的贡献）。另外，可以用 `vector` 做 key 方便代码编写。
+这里在比赛时写得非常混乱，是因为没有处理好边界重复的情况。如果设定好加在两端的字符都至少有一个，则这样子并不会出现重复（需要额外加上开头结尾是同一段的贡献）。另外，可以用 ''vector'' 做 key 方便代码编写。
 总时间复杂度 $O(\Sigma ^2 n \log n)$，勉强能过。
@@ 行 42: / 行 74: @@
 总时间复杂度 $O(\Sigma ^2 n)$。
+===== D - Dividing Strings =====
+Solved by Potassium.
+==== 题目描述 ====
+给一个数字串，求划分为一堆数字，使得这堆数字的极差最小。$2\le n\le 10^5$。
+==== 解题思路 ====
+重要但显然的结论：答案不超过 $9$。
+枚举第一段长度进行暴搜，用双哈希+前缀和比较大小即可。复杂度是调和级数，$O(n\log n)$。

2020-2021/teams/i_dont_know_png/multi2020-nowcoder-4.1595289231.txt.gz · 最后更改: 2020/07/21 07:53 由 qxforever