2023-07-02

UOJ Round #4

A. 元旦三侠的游戏

$n = 2$

必有 $a = 2, b = 1$。

不可以，总司令！

$n \le 1000$

这是一个博弈问题，记 $f_{a, b}$ 表示状态是否必胜。

使用记忆化搜索进行转移，$b$ 上界为 $\log n$，状态数为 $\mathcal O(n \log n)$。

$n \le 10^9$

保证 $a \ge 2, b \ge 1, a^b \le n$，于是有 $a \le \sqrt[b]{n}, b \le \log_a n$。

显然 $a, b$ 的范围是相互制约的，那么实际状态数只有 $\sum_{b = 1}^{\log n} \sqrt[b]{n}$。

如果一个状态 $(a, b)$ 满足 $a \gt \sqrt[b + 1]{n}$，那么此时 $b$ 是不能再增加了，那么只需考虑 $\lfloor \sqrt[b]{n} \rfloor - a$ 的奇偶性即可得到答案。

注意当 $b = 1$ 时 $\sqrt[b]{n} = n$，而 $b = 2$ 时 $\sqrt[b]{n} = \sqrt n$，因此我们对 $b = 1$ 的情况作特殊判断。

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

THUSC 2023 试机题。

$n_a, n_b, n_c \le 30$

查出 $a, b, c$ 的所有元素并排序。

第 $k$ 大显然二分答案。

由于可能存在重复数字，因此需要找到一个尽可能大的数，使得各序列中小于它的元素个数和小于 $k$。

最坏情况下总调用次数为 $\lceil \log_2 w \rceil \times \lceil \log_2 n \rceil \times 3 = 30 \times 17 \times 3 = 1530$。

特判 Test #1。

或者加一个小优化，内部二分的区间随外部二分的区间转移。

$n \le 5, k \le 10$

暴搜出所有长度 $\le k$ 的可能路径。

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

$n \le 100, k \le 100$

记 $w(a)$ 表示 $a$ 序列的权值。

将序列抽象成点，每一个序列向它最后添加一个点形成的序列连边，那么这张图满足堆性质：如果 $u$ 连向 $v$，则 $w(u) \lt w(v)$。

使用堆维护已拓展的序列，一开始将所有入度为 $0$，即长度为 $1$ 的序列加入堆中，重复 $k$ 次操作：每次取出一个权值最小的序列并输出其权值，将其连向的序列加入堆中。

每个点度数为 $n$，时间复杂度 $\mathcal O(nk \log nk)$。

$n \le 1000, k \le 10^5$

使用孩子兄弟表示法，将每个点度数减至 $2$。

为了保证权值递增，需要将每个序列扩展后的序列按权值排序。

事实上每个序列可扩展的状态只与最后一个元素有关，对每个点预处理即可。

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