Comet OJ – Contest #9 & X Round 3 题解

作者: xht37 分类: 题解 发布时间: 2019-08-27 11:31

点击数:823

Comet OJ – Contest #9 & X Round 3

【XR-3】等差数列

by xht37 & NaCly_Fish

前置知识

  • 模拟或等差数列求和

方法一

因为一共只有 $n \le 10^6$ 项,所以可以把数列的每一项都求出来然后相加即可,时间复杂度 $\Theta(n)$。

方法二

根据前两项的值算出公差,就可以求出第 $n$ 项,然后用等差数列求和公式 $S=\frac{(a_1+a_n)n}{2}$ 计算即可,时间复杂度 $\Theta(1)$。

【XR-3】小道消息

by meaningful & NaCly_Fish

前置知识

  • 简单数论

本题题解

如果 $k + 1$ 是质数且 $2(k+1)>n+1$,则答案为 $1$,因为它一定与 $2 \sim n+1$ 的数(除了自己本身)互质。

否则答案为 $2$,因为根据伯特兰-切比雪夫定理,$k+1$ 一定与 $2 \sim n+1$ 中最大的质数互质,因此第一天衣服上写有这个最大质数的人一定会得到这条小道消息,那么在第二天所有人都会知道。

时间复杂度即为判断质数的时间复杂度,$\Theta(\sqrt n)$ 即可。

【XR-3】核心城市

by meaningful

前置知识

  • 树的直径与树的中心

本题题解

如果 $k =1$,则唯一的核心城市显然为树的中心(若直径上有偶数个点,则任意选择中间两个点中的一个)。

当 $k \ne 1$,我们可以把树的中心当成根,然后我们依次将点贪心地加入核心城市中。

定义 $f_x$ 为以树的中心为根时,点 $x$ 离自己子树中的叶子的最大距离。

那么,我们可以每次在与当前确定的核心城市相连的非核心城市中选择 $f$ 最大的城市加入到核心城市中,直到核心城市的数量到 $k$ 为止。这可以用堆实现,时间复杂度 $\Theta(n \log n)$。

【XR-3】系统设计

by PinkRabbit

前置知识

  • 字符串 Hash
  • 树状数组/线段树上二分

本题题解

将树上根到节点 $u$ 的简单路径依次经过的边的排名记作一个字符串 $s_u$。

例如上图中,有:

$$
\begin{aligned}
s_1&=\texttt{“”}(空串)\\
s_2&=\texttt{“1”}\\
s_3&=\texttt{“11”}\\
s_4&=\texttt{“111”}\\
s_5&=\texttt{“2”}\\
s_6&=\texttt{“12”}\\
s_7&=\texttt{“121”}\\
s_8&=\texttt{“122”}\\
s_9&=\texttt{“21”}\\
s_{10}&=\texttt{“22”}\\
\end{aligned}
$$

考虑询问 1 x l r 时,将 $a_{l..r}$ 也看作一个字符串,并在前面拼上 $s_x$ 这个字符串。

则转化为查询 $str=s_x+a_{l..r}$ 在树中最长能够匹配到哪个点。

举个例子,若 $x=2,a_{l..r}=\texttt{“231”}$,则 $str=s_2+a_{l..r}=\texttt{“1231”}$。

最长能匹配上 $s_6=\texttt{“12”}$,则答案为 $6$。

考虑字符串哈希,预先处理所有节点表示的字符串的哈希值,并存在哈希表里。

用数据结构维护序列的哈希值,查询时在数据结构上二分,在哈希表中查询是否存在此值即可。

时间复杂度 $\Theta((n+(m+q)\log m)\times T(\mathrm{hash}))$。

【XR-3】Namid[A]me

by EntropyIncreaser

首先介绍如何快速计算 $x^x \bmod P$。注意到模数 $P = 786433$ 非常小,且在题目中给出了模数的一个原根,因此我们可以轻松在 $\Theta(P)$ 的时间内预处理出 $1 \sim P – 1$ 每个数的离散对数 $ind[x]$ 以及幂 $pow[k] = g^k \bmod P$。通过欧拉定理即可在 $\Theta(1)$ 时间内计算 $x^x = pow[ind[x] x \bmod (P – 1)]$。需要特判 $x \equiv 0 \pmod P$ 的情况。

接下来考虑一条链如何计算。

这样所有链都等价于一个区间,考虑枚举右端 $r$,那么对于 $[l, r]$ 内所有数的与设为 $x_l$,注意到若 $x_l \neq x_{l + 1}$,由于 $x_l = x_{l+1} \operatorname{\texttt{and}} a_l$,那么必然是至少在 $x_{l+1}$ 中的一个二进制位从 $\texttt{1}$ 变为 $\texttt{0}$。因此,从 $x_l$ 到 $x_1$,必然最多只有 $w + 1$ 种取值。我们考虑只维护被取到的值分别取到了多少次即可。

接下来注意对于一个有 $d$ 个叶子的子树,在维护时子树内每个节点到子树的根的路径上的与和总共不超过 $d(w+1)$ 种取值,这是因为将每个叶子到根的一条链内的取值各自都不超过 $w + 1$。我们只需在 DFS 的过程中维护每个子树内所有能取到的值的出现次数即可。这一部分的复杂度为 $\Theta(ndw)$。在处理子树的时候,我们还需计算路径两端点在不同子树的路径的答案,这一部分我们暴力枚举,注意到两个叶子只会在它们的 LCA 位置为合并的复杂度贡献 $(w+1)^2$,因此计算这一部分答案的总代价为 $\Theta((dw)^2)$。但是同时又有另一个显然的上界:$\Theta(n^2)$,因为只有这么多条路径,而在 $nd$ 总体有限制的这一条件下,考虑不等式 $\min(a, b) \le \sqrt{ab}$,可知这一部分的复杂度不超过 $\Theta(\min(n, dw) ^2) \le \Theta(ndw)$。

综上所述,本算法的复杂度为 $\Theta(ndw)$。

【XR-3】Unknown Mother-Goose

by Shadowice1984

题目的数据范围很具有迷惑性,可能会让人认为标算是 $\Theta(2^s)$ 的容斥,而 $n$ 只有 $10^9$ 则是为了避免解同余方程时爆 long long。

其实标算是 bitset 大暴力啦。

一个可能的暴力是:开一个长度是 $10^9$ 的布尔数组 $a$,把是 $S$ 中每一个元素的倍数的下标全部赋值成 $1$,那么,如果 $a_x,a_{x-1},a_{x+1}$ 都是 $1$,$x$ 就是合法的。

如果把暴力中的布尔数组用 bitset 存储,问题就变成了数 bitset 里有几组三个连续的 $1$,你可以通过一套 & 操作转化为数 popcount。

不过还可以每 $64$ 位分一块,块内算一下内部有几组三个连续的 $1$,然后算块和块之间有几组三个连续的 $1$,这个枚举一下即可。

这样的复杂度是 $\Theta(\frac{n}{8})$ 的,因为 popcount 的底层实现实际上是查 $65536$ 长度的表。

下面是如何生成这个 bitset,暴力并不清楚能不能过,因为可以去重,加上特判 $1$ 之后胡乱暴力。

为了跑的快点,你可以根据 $S$ 中的元素是否大于 $64$ 来分情况讨论 ,如果大于 $64$ 那么暴力的赋值,如果小于等于 $64$,每一块实际上被按位或的 01 串很快就会出现循环节,直接预处理出这些循环的 01 串,然后按位或即可。

总时间复杂度 $\Theta(\frac{n|S|}{64} + \frac{n}{8})$。

理论复杂度算起来很高,但是寻址连续并且不会频繁调用系统栈(对比大家平时写的算法),所以可以很快的通过。

顺便说一句,建议手写 bitset。

发表评论

电子邮件地址不会被公开。 必填项已用*标注