UOJ Round #20

• A. 跳蚤电话
  • 9
  • 20
  • 34
  • 100
• B. 机器蚤分组
  • 9
  • 27
  • 48
• C. 金坷垃
  • 3
  • 18

A. 跳蚤电话

9

$n \le 10$

暴搜。

20

$n \le 20$

状压 DP。

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

34

从 $1$ 号城市到任意城市的最短通信路径上城市个数不超过 $3$

手玩公式。

100

$n \le 10^5$

\[f_i = \prod\limits_{j \in subtree_i} \frac{1}{size_j} (1 + \sum \limits_{k \in son_j} \frac{size_k}{size_j - size_k})\]

预处理逆元。

时间复杂度 $\mathcal O(n)$。

B. 机器蚤分组

9

$n, q \le 10$

暴搜。

27

$n, q \le 100$

使用网络流求解 DAG 最小链覆盖。

48

$n, q \le 1000$

根据 Dilworth定理，最小链覆盖等于最长反链。

容易发现可以选择某个长度 $len$ 的所有子串作为一个极长反链，大胆猜测对不同的 $len$ 取最大值就是最长反链。

使用 SA 计算每个长度的不同子串个数。

时间复杂度 $\mathcal O(q n \log n)$。

C. 金坷垃

3

$\forall 1 \le i \lt n, a_i + m \le a_{i + 1}$

输出 $a_i + \frac{m}{2}$。

18

$\forall 1 \le i \lt n, a_i = a_{i + 1}$

一个结论，$n$ 个 $[0,1]$ 随机实数第 $i$ 小的期望是 $\frac{i}{n + 1}$，答案为 $a + \frac{m_i}{n + 1}$。