LibreOJ β Round #5 题解

liu_cheng_ao 2017-10-08 17:09:33 2018-04-07 17:51:48

T1.自然语言

By CommonAnts,题解 By CommonAnts

  • 考察选手对递归的理解和建模能力,DP 优化也可以解决。实际上是个上下文无关文法。
  • 贪心或自动机或 DP
  • 思维难度:提高
  • 实现难度:普及

算法一

枚举出所有长度不超过 n 的合法串。需要较精细的实现。

时间复杂度: O(n\mathrm{Fib}_n)

空间复杂度: O(n\mathrm{Fib}_n)

其中 \mathrm{Fib}_n 表示斐波那契数的第 n 项。

预计得分: 17

算法二

枚举最开始一步的操作,将串按 N 所对应的段分开递归进行。

f(l,r) 表示 [l,r] 子区间是否满足语言结构。枚举第一次操作时 V 的位置,区间 DP 即可。

转移方程为 f(l,r)=(\mathop{\lor}\limits_{k\in (l,r),s_k=V}f(l,k-1)\land f(k+1,r))\lor ([s_l=V]\land f(l+1,r))\lor ([s_r=V]\land f(l,r-1)) 。对于中文去掉 [s_l=V]\land f(l+1,r) 一项即可。

可以通过按 V 讨论转移等方法优化。

时间复杂度: O(n^2\sim n^3)

空间复杂度: O(n^2)

预计得分: 41\sim 65

算法三

考虑上述DP的优化。

对于英语,注意到当区间端点为 V 时,必定有一步 N\rightarrow (VN|NV) 的操作产生这个 V。不妨认为这是区间内的第一步,所以可以直接消掉端点的 V。也就是只需考虑端点不是 V 的状态。(注意空串不合法)

故而,对于连续的一段 V,可以缩成一个,因为决策过程中这一段 V 中无论最早生成哪个两边的 V 都会成为区间的一端,所以这段 V 只能用一次,和缩成一个 V 产生的效果相同。

对于汉语类似,不过注意到区间左端点是 V 必定无解,因而缩起的这个 V 其实指区间内最右一个,只有用它分开序列后不会出现左端点是 V 的情况。

子任务 4 缩 V 之后规模很小,可以使用算法二。

时间复杂度: O(n^3~n^2)

空间复杂度: O(n^2)

预计得分: 13 ,结合前述可得 54\sim 78

算法四

首先合法序列不可能有连续两个 N。用数学归纳法即可证明。

用算法三的方法缩 V 之后就会变成 NV 交错的序列。

考虑 NV 交错的情况。

对于英语,只需不断执行 N\rightarrow NVN 即可得到两端是 N 的任意长交错序列,再以 N\rightarrow NV N\rightarrow VN 调整端点即可,故除单个 V 外一定符合。

对于汉语类似,但左端点必须是 N

时间复杂度: O(n)

空间复杂度: O(n)

预计得分: 100

算法五

另一种理解

对于英语,若最左端或右端是 V 则删去之不影响可构造性;否则要么此时的序列是单个 N,要么第一步是 NVN

考虑最右的由 N\rightarrow NVN 产生的 V。若这个 NVN 不是第一步,考虑生成它的前一个 NVN。这两个 NVN 之间必定全为 VN

可以把最右的 NVN向上调整。如此往复即可将其调整为第一个 NVN

S\rightarrow V*SV+NV* ,解得 V*N(V+N)*V*

汉语类似可得 S\rightarrow SV+NV* ,解得 N(V+N)*V*

贪心匹配或建 DFA 即可。

sol.png

时间复杂度: O(n)

空间复杂度: O(n)

预计得分: 100

T2.最小倍数

By tangjz,题解 By tangjz

  • 考察选手对初等数论的理解与使用,基础知识为阶乘质因数分解,可以结合二分法、数位贪心解决。
  • 二分法或数位贪心
  • 思维难度:提高
  • 实现难度:提高

算法一

注意,以下算法均假设选手会计算前 100 个质数分别是几,如有疑问请参考质数定理、质数筛法。

枚举答案 n ,对于每个 \mathrm{pr}_i 检查是否满足 n! \bmod \mathrm{pr}_i^{e_i} = 0 。具体实现时,可以找到最大的 \alpha_i 使得 \mathrm{pr}_i^{\alpha_i} \mid n! ,检查是否有 \alpha_i \geq e_i 即可。

计算 \alpha_i 有一个很简单的方法:从 1 \times 2 \times \cdots \times N 中提取出 \mathrm{pr}_i 的倍数,并从每个倍数中提取出一个 \mathrm{pr}_i ,剩下可能含有 \mathrm{pr}_i 的倍数的部分是 1 \times 2 \times \cdots \left \lfloor \frac{N}{\mathrm{pr}_i} \right \rfloor ,变成类似的子问题。整理一下可得 \alpha_i = \sum_{k = 1}^{\infty}{\left \lfloor \frac{N}{\mathrm{pr}_i^k} \right \rfloor}

根据 \alpha_i 的计算方式也可以估计出答案上界是 a_i

时间复杂度: O(T m \max(a_i))

空间复杂度: O(1)

预计得分: 10

算法二

注意到一个事实,对于 N = v - 1 N = v ,如果 \alpha_i 不相同,则一定有 \mathrm{pr}_i \mid v 。虽然 \alpha_i 的差异可能不只变化了 1 ,但是对于 \alpha_1, \alpha_2, \cdots 变化的次数,从 N = 1 N = v 一定是 O(\sum_{i = 2}^{v}{\tau(i)}) = O(v \log v) 的,其中 \tau(i) 表示 i 的约数个数。

读入所有的输入数据,尝试动态维护每组数据还剩下多少个 \mathrm{pr}_i 不满足 \alpha_i \geq e_i ,只需要对于每个 \mathrm{pr}_i 将来自不同组数据的 e_i 排升序,在增大 \alpha_i 的同时用指针扫相应的 e_i 即可维护每组数据的剩余信息,当某组数据没有不满足条件的 \mathrm{pr}_i 时,也就找到了相应的答案 N

时间复杂度: O(\max(a_i) \log \max(a_i) + T m \log T)

空间复杂度: O(T m)

预计得分: 35

算法三

枚举答案是一件很暴力的事情,既然知道了答案的上界是 a_i ,那么二分答案也变成了一件很显然的事情。

对于每组数据,二分答案后,每次计算 \alpha_i 的复杂度是 O(\log_{\mathrm{pr}_i} N) ,总的时间复杂度看上去是带有两个 \log 的,但实际上跑得不慢,很可能得到满分。

另外一种二分的方法是边枚举质数边二分,根据前 i - 1 个质数得到一个下界,在枚举第 i 个质数的时候使用之前的下界和现在的上界继续二分,期望复杂度会得到很大改善。

时间复杂度: O(T m \log^2 a_i)

空间复杂度: O(m) O(1)

预计得分: 65 \sim 100

算法四

注意到 \alpha_i = \sum_{k = 1}^{\infty}{\left \lfloor \frac{N}{\mathrm{pr}_i^k} \right \rfloor} 这个式子是可以并行计算的,换句话说,将 N 写成 \mathrm{pr}_i 进制,不同位上的数字对 \alpha_i 的贡献互不影响,可以分别计算再累加起来。

更具体来说,令 (x_1 x_2 \cdots x_m)_{p} 表示 \sum_{i = 1}^{m}{x_i p^{m - i}} p 进制下的数字,那么 N \mathrm{pr}_i 进制下的某个数位 v \cdot \mathrm{pr}_i^k \alpha_i 的贡献将会是 (v v \cdots v)_{\mathrm{pr}_i} (共 k v ),因此可以确定第 k 个数位对 \alpha_i 的贡献,从而可以按照 \mathrm{pr}_i 进制下从高位到低位枚举的顺序贪心地找到一个最小的 N 满足 \alpha_i = e_i ,取这些 N 1 的最大值即可得到答案。

从时间复杂度来看,算法四相当于算法三去掉二分的一个 \log ,然而更多人选择了算法三 + 卡常通过此题。

时间复杂度: O(T m \log a_i)

空间复杂度: O(\log a_i)

预计得分: 100

T3.游戏

By CommonAnts,题解 By CommonAnts

  • 考察选手组合游戏胜负的判断,基环树的处理和实现细节。
  • 基环树上 DP
  • 思维难度:提高+
  • 实现难度:提高+

算法一

大力手算,分类讨论。

时间复杂度: O(n+q)

空间复杂度: O(n^n)

预计得分: 15

算法二

首先你要会处理带平局的组合游戏。按不带平局的方法更新所有能更新的状态(能到达必败态的为必胜态,只能到达必胜态的为必败态),剩下的全是平局。

状态用当前位置表示即可,每次询问重算。

时间复杂度: O(nq)

空间复杂度: O(n)

预计得分: 42

算法三

建立模型,从 i f[i] 连边。

到达的性质其实就是告诉你基图联通,换句话说就是形成基环内向树(博弈的决策树是所有边取反得的基环外向树)。

另外询问的性质等价于两个点都在环上。

f[] 是排列,则图是个环。修改时变成环+链。

先判断链长的奇偶性,若为偶数,则环上为平局;若非平局,判断与链端距离的奇偶性即可。

时间复杂度: O(n+q)

空间复杂度: O(n)

预计得分: 22 ,结合前述可得 64

算法四

若一个点在外向树上的子节点有必败态,它必定必胜;否则必定不向外向树转移。这样可以发现外向树的作用就是使得某些环上的点必胜。

同样地,询问时先判断链上最近能确定状态(端点或必胜)节点和环距离的奇偶性,以确定是否平局。若非平局则判断其和最近能确定状态(端点或必胜)节点距离的奇偶性。

时间复杂度: O(n+q)

空间复杂度: O(n)

预计得分: 100

T4.随机数列

By tangjz,题解 By tangjz

  • 考察选手对调和级数的理解,以及对区间和的运用。
  • 枚举 + 前缀和
  • 思维难度:提高+
  • 实现难度:提高

算法一

注意到求期望的做法和求出所有情况取值之和的做法没有什么不同,生成 X_i 所在的序列 A X_j 所在的序列 B ,枚举并计算即可,注意浮点误差,可以将所求式子化为 \left \lceil \frac{X_i^2 + X_j^2}{X_i X_j} \right \rceil 用整数计算。

时间复杂度: O(R_1 R_2)

空间复杂度: O(R_1 + R_2)

预计得分: 10

算法二

注意到生成的 X_i X_j 取值都很小(不超过 C ),所求式子的答案也不会很大,根据对勾函数的特性甚至可以知道 \left \lceil \frac{X_i}{X_j} + \frac{X_j}{X_i} \right \rceil 的上界就是 (C + 1)

不妨设 \left \lceil \frac{X_i}{X_j} + \frac{X_j}{X_i} \right \rceil = k ,考虑枚举 k 来统计 (X_i, X_j) 的数量,从而得到答案。对于 X_i = p 的情况,有 \frac{X_i}{X_j} \leq p \frac{X_j}{X_i} \leq \frac{C}{p} ,直接枚举 X_i k 是行不通的,但是如果有 X_i \leq X_j ,便可以将枚举 X_i 后枚举 k ,统计 X_j 数量的问题做到 O(\sum_{p = 1}^{C}{\frac{C}{p}}) = O(C \log C) 的复杂度,而对于 X_i > X_j 的情况,则可以枚举 X_j 后枚举 k 再统计 X_i 的数量。

具体统计数量时得到的是 X_j (或 X_i )取值位于某个区间的数字数量,可以用 O(C) 的空间计算前缀和,从而快速查询到区间和。

时间复杂度: O(R_1 + R_2 + C \log C)

空间复杂度: O(R_1 + R_2 + C)

预计得分: 30

算法三

注意到随机序列的取值只有 C 种,且 X_{i + 1} 仅取决于 X_i 和其他常量。尝试建立一个 C 个点的图, X_i X_{i + 1} 连边,则会得到一个连通的基环树,且只会有至多一个入度为 0 的点。找到这样一个类似 \rho 的形状后即可统计出 X_i X_j 取每种值分别有多少种可能,再用 O(C) 的空间计算这些数量的前缀和即可。注意这个图的形状可能是 \rho

然而算法依旧存在超时的可能,但已经不是算法层面上的问题,而是实现上的问题。除了一些写错细节的情况,还有可能造成超时的原因是浮点数运算量过大,毕竟枚举 X_i k 后,要解一个一元二次不等式才能得到 X_j 的取值范围,这里可以发现,对于固定的 k ,解一定是关于 \frac{X_j}{X_i} 的式子,可以预处理这样的系数,一定程度上降低浮点运算的次数,不能降低的部分则可以尝试用整数除法代替。

时间复杂度: O(C \log C)

空间复杂度: O(C)

预计得分: 60 \sim 100