比赛链接

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) $$

Solved by nikkukun.

水题不表。

Upsolved by nikkukun.

定义 $f(S, x, y)$ 是一个长度为 $y - x + 1$ 的串，且字符依次为 $S[x:x]$ 的最大值、$S[x:x + 1]$ 的最大值……$S[x : y]$ 的最大值。求 $f(f(S, x_1, y_1), x_2, y_2)$ 有多少种本质不同的串，其中 $[x2, y2] \subseteq [x1, y1] \subseteq [1, n]$。

显然 $f(S, x_1, y_1)$ 必然是个串中字符递增的东西，然后递增东西里取 $f$ 等于原串，故相当于问所有 $f(S, x_1, y_1)$ 有多少种本质不同的子串。同时枚举每个位置 $x$，发现实际上只需要求 $f(S, x, n)$，而其他 $f(S, x, \ast)$ 都是它的一个子串。因此，可以利用序列自动机求出 $f(S, i, n),\ i = 1, 2, \ldots, n$，这 $n$ 个串本质不同的子串个数就是答案。

注意到这样的串可以用一个十元组唯一表示，因此可以枚举子串的开头结尾字符分别是十元组的哪两个位置，并按照这两个位置中间的子元组进行分类，计算出对一段中间固定的子元组，向左右添加字符可以构成什么串。这个问题相当于求二维平面上一些点向左下构成的矩形中，一共覆盖了多少个整点。

这里在比赛时写得非常混乱，是因为没有处理好边界重复的情况。如果设定好加在两端的字符都至少有一个，则这样子并不会出现重复（需要额外加上开头结尾是同一段的贡献）。另外，可以用 vector 做 key 方便代码编写。

总时间复杂度 $O(\Sigma ^2 n \log n)$，勉强能过。

参考解题思路 1，如果能把 $f(S, i, n),\ i = 1, 2, \ldots, n$ 全插到 SAM 里，那就能直接求答案，可惜字符串长之和是 $O(n^2)$ 的。

考虑倒序建 trie。在 trie 上行走时，一旦有某个字母被新插入的字母更新了，则 trie 上会从原点向右多出来一条仅有一种字母的新链。对于每个位置而言，它只会被这样向右移动到新链上 $O(\Sigma)$ 次，故 trie 中最多 $O(\Sigma n)$ 个节点，于是可以跑广义 SAM 了。

总时间复杂度 $O(\Sigma ^2 n)$。

Solved by Potassium.

给一个数字串，求划分为一堆数字，使得这堆数字的极差最小。$2\le n\le 10^5$。

重要但显然的结论：答案不超过 $9$。

枚举第一段长度进行暴搜，用双哈希+前缀和比较大小即可。复杂度是调和级数，$O(n\log n)$。

Solved by nikkukun.

有平行线 $AB \parallel CD$ 或 $AB \parallel DC$，给出 $AC, AD, BC, BD$ 的长度，判断是哪种情况。

可以先判断 $C$ 和 $D$ 在 $AB$ 中线的哪一侧，然后分类讨论。标程的做法是 $AB \parallel CD$ 当且仅当 $AD$ 或 $BC$ 为四边中的最大值。

Solved by qxforever.

对 $1$ ~ $n$ 的数两两分组，使得组数尽可能多，且每组的两个数不互质，输出方案。

显然大于等于 $\lceil n/2 \rceil$ 的质数和 $1$ 无法分组，其他的数均可以分组。下面是一种方案。

对每个数，先塞到其最大质因数的桶中。对最大质因数 $p < \lceil n/2 \rceil$ 的桶，其大小至少为 $2$。若为偶数，则桶内互相匹配；若为奇数，则将 $2p$ 扔到 $2$ 的桶中，其他的数互相匹配。这样最多只有 $1$ 个数不能匹配，是最优的。

老原题了

Solved by qxforever.

有 $n$ 个部队，$m$ 个军团，每个部队属于一个军团。每个部队所属的军团是随机生成的。现在告诉你任意两个部队是否属于同一个军团，但是每条信息都有 $\frac{1}{S}$ 的概率是错误的。已知 $n$，$S$，以及 $\frac{n(n-1)}{2}$ 条信息，还原出每个部队所属军团的情况。$30\le n\le 300,20\le S\le 100,1 \le m\le \lfloor n/30 \rfloor$ 。

注意到 $\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)$ 。