UOJ Logo EntropyIncreaser的博客

博客

2020年北京青少年信息学科普日市级活动(初中组)题解

2020-11-05 13:06:37 By EntropyIncreaser

T1 生命游戏(gol)

注意到只有 $2^{4\times 4}$ 种输入,我们可以先枚举每种输入确立其下一个状态,然后倍增或者通过内向树处理都是可以的。

时间复杂度 $\Theta(states\log T + Q\log T)$ 或者 $\Theta(states + Q)$。

T2 装备升级(upgrade)

性质 A

我们容易发现这样一个事实:不可能有两个装备恰好是一级,否则一定可以将一个升级挪到另一个上。

因此可以导出这一性质:

  • 若 $m$ 是偶数,那么一定是选 $w_1 + w_2$ 前 $m/2$ 小的。

  • 若 $m$ 是奇数,那么要么是选前 $\lfloor m/2\rfloor$ 小的 $w_1+w_2$,再在剩下的里面选一个一级,要么是选前 $\lceil m/2\rceil$ 小的 $w_1+w_2$,再在这些里面退掉一个二级。

因此我们先按照 $w_1+w_2$ 排序,然后枚举就可以了。

性质 B

我们考虑贪心选取最小的 $m$ 个 $w$,不难发现他们一定是可以满足要求的。因此只需一次 $\texttt{nth_element}$,可以做到 $\Theta(n)$。

std

我们考虑 $w_1\le w_2$ 和 $w_1>w_2$ 已经涵盖了所有可能性,我们考虑对于两拨分别算出所有 $m$ 的答案,之后枚举一边实际选了几个就可以了。

对于性质 A,我们可以用前后缀 $\min$ 来加速,对于性质 B,我们只需要排序之后做一遍前缀和即可。

因此总共复杂度瓶颈为排序,$\Theta(sort(n))$。

T3 因子统计(divisor)

我们注意到如果一个数的质因子分解是 $p_1^{k_1} \cdots p_n^{k_n}$,那么因子数量就是 $(k_1+1)\cdots (k_n+1)$。

std

考虑一个莫队,我们在 $(n,m)$ 的移动过程中维护 $\binom n m$ 的质因子分解中 $> \sqrt n$ 的那部分,这样每次移动只会有 $\Theta(1)$ 个质因子增减。最后统一统计 $\le \sqrt n$ 的质因子贡献,因为总共只有 $\pi(\sqrt n) = \Theta \left( \frac{\sqrt n}{\log n}\right)$ 个质数,我们每个质数暴力做就是 $\Theta(\sqrt n)$ 的了。复杂度是 $\Theta(q\sqrt n + n\sqrt q)$。

bonus

本题可以做到……的复杂度?

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。