UOJ Round #5

• A. 怎样提高智商
  • 20
  • 30
  • 100
• B. 怎样更有力气
  • 10
  • 40
• C. 怎样跑得更快
  • 5
  • 20
  • 40
  • 50

A. 怎样提高智商

20

$n \le 3$

手算。

30

$n \le 4$

暴搜。

100

$n \le 10^5$

$n \le 4$ 时的答案为 $4, 12, 36, 108$，大胆猜测答案为 $4 \times 3^{n - 1}$。

尝试构造解。

$i$. 编号小于 $i$ 的题目中你一共选了几个 A？
A. $0$ 个 B. $0$ 个 C. $0$ 个 D. $0$ 个

前 $n - 1$ 道只能选 B、C、D，第 $n$ 道随便选。

B. 怎样更有力气

10

$n \le 100$
$m \le 100$
$p \le 100$

将所有边建出来跑最小生成树。

时间复杂度 $\mathcal O(n^3)$（视 $n, m, p$ 同阶）。

40

$n \le 300000$
$m \le 300000$
$p = 0$

没有限制关系就好办了。

每天可以连通的点集即为树上 $u, v$ 两点间路径上的点集，将这条路径对 $w$ 取 $\min$，最后再求边权和。

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

C. 怎样跑得更快

5

$n \le 3$
$q = 1$

手推式子。

20

$n \le 100$
$q \le 100$

对每个询问进行高斯消元。

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

40

$n \le 100$ $q \le 1000$

使用高斯消元求矩阵逆推出公式。

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

50

$c = d$

\[\begin{aligned} \sum_{j = 1}^n \gcd(i, j)^c \cdot \text{lcm}(i, j)^c \cdot x_j & \equiv b_i \pmod p \\ \sum_{j = 1}^n i^c j^c \cdot x_j & \equiv b_i \pmod p \\ \sum_{j = 1}^n j^c \cdot x_j & \equiv \frac{b_i}{i^c} \pmod p \end{aligned}\]

左侧与 $i$ 无关，右侧与 $j$ 无关。

检查 $b$ 是否满足任意 $\frac{b_i}{i^c}$ 都相等，若相等则输出一组解（比如 $b_1, 0, \cdots, 0$，否则无解。