2020-2021:teams:i_dont_know_png:multi2020-nowcoder-4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-4 [2020/07/21 05:14] 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 | 比赛链接]] | [[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)$，勉强能过。 | 总时间复杂度 $O(\Sigma ^2 n \log n)$，勉强能过。 | ||
| 行 42: | 行 74: | ||
| 总时间复杂度 $O(\Sigma ^2 n)$。 | 总时间复杂度 $O(\Sigma ^2 n)$。 | ||
| + | |||
| + | |||
| + | ===== D - Dividing Strings ===== | ||
| + | |||
| + | Solved by Potassium. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个数字串，求划分为一堆数字，使得这堆数字的极差最小。$2\le n\le 10^5$。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 重要但显然的结论：答案不超过 $9$。 | ||
| + | |||
| + | 枚举第一段长度进行暴搜，用双哈希+前缀和比较大小即可。复杂度是调和级数，$O(n\log n)$。 | ||
| + | |||
| + | |||
| 行 73: | 行 123: | ||
| 对每个数，先塞到其最大质因数的桶中。对最大质因数 $p < \lceil n/2 \rceil$ 的桶，其大小至少为 $2$。若为偶数，则桶内互相匹配；若为奇数，则将 $2p$ 扔到 $2$ 的桶中，其他的数互相匹配。这样最多只有 $1$ 个数不能匹配，是最优的。 | 对每个数，先塞到其最大质因数的桶中。对最大质因数 $p < \lceil n/2 \rceil$ 的桶，其大小至少为 $2$。若为偶数，则桶内互相匹配；若为奇数，则将 $2p$ 扔到 $2$ 的桶中，其他的数互相匹配。这样最多只有 $1$ 个数不能匹配，是最优的。 | ||
| + | [[https://codeforces.com/contest/449/problem/C|老原题了]] | ||
| ===== I - Investigating Legions ===== | ===== I - Investigating Legions ===== | ||
| 行 85: | 行 136: | ||
| 注意到 $\frac{n}{m}\ge 30$，说明每个军团都有约 $30$ 个部队，且 $S$ 比较大，不会显著的影响结果。 | 注意到 $\frac{n}{m}\ge 30$，说明每个军团都有约 $30$ 个部队，且 $S$ 比较大，不会显著的影响结果。 | ||
| - | 设当前最小的没有确定军团的部队为 $x$，选取所有 `a[x][i]=1` 的部队 。看这些部队之间的 `a` 是否相同，如果 `a[x][i]`是错误的信息，那么他和其他的部队关系总会是 $0$ 。之后再从 `a[x][i]=0` 中找剩下的部分，看他和这些部队的关系是否总是 $1$ 即可。单组数据时间复杂度为 $O(m\times n^2)$ 。 | + | 设当前最小的没有确定军团的部队为 $x$，选取所有 ''a[x][i]=1'' 的部队 。看这些部队之间的 ''a'' 是否相同，如果 ''a[x][i]'' 是错误的信息，那么他和其他的部队关系总会是 $0$ 。之后再从 ''a[x][i]=0'' 中找剩下的部分，看他和这些部队的关系是否总是 $1$ 即可。单组数据时间复杂度为 $O(m\times n^2)$ 。 |
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-4.1595279697.txt.gz · 最后更改: 2020/07/21 05:14 由 qxforever
