LibreOJ β Round #5 题解

liu_cheng_ao 于 2017-10-08 17:09:33 发表,2017-10-23 19:20:20 最后更新

T1.自然语言

By CommonAnts,题解 By CommonAnts

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

算法一

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

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

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

其中 Fibn\mathrm{Fib}_nFibn 表示斐波那契数的第 nnn 项。

预计得分:171717

算法二

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

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

转移方程为 f(l,r)=(k(l,r),sk=Vf(l,k1)f(k+1,r))([sl=V]f(l+1,r))([sr=V]f(l,r1))。对于中文去掉 [sl=V]∧f(l+1,r)[s_l=V]\land f(l+1,r)[sl=V]f(l+1,r) 一项即可。

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

时间复杂度:O(n2∼n3)O(n^2\sim n^3)O(n2n3)

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

预计得分:41∼6541\sim 654165

算法三

考虑上述DP的优化。

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

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

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

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

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

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

预计得分:131313,结合前述可得 54∼7854\sim 785478

算法四

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

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

考虑 NV 交错的情况。

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

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

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

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

预计得分:100100100

算法五

另一种理解

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

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

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

S→V∗SV+NV∗S\rightarrow V*SV+NV*SVSV+NV,解得 V∗N(V+N)∗V∗V*N(V+N)*V*VN(V+N)V

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

贪心匹配或建 DFA 即可。

sol.png

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

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

预计得分:100100100

T2.最小倍数

By tangjz,题解 By tangjz

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

算法一

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

枚举答案 nnn ,对于每个 pri\mathrm{pr}_ipri 检查是否满足 n!modpreii=0。具体实现时,可以找到最大的 αi\alpha_iαi 使得 priαi∣n!\mathrm{pr}_i^{\alpha_i} \mid n!priαin!,检查是否有 αi≥ei\alpha_i \geq e_iαiei 即可。

计算 αi\alpha_iαi 有一个很简单的方法:从 1×2×⋯×N1 \times 2 \times \cdots \times N1×2××N 中提取出 pri\mathrm{pr}_ipri 的倍数,并从每个倍数中提取出一个 pri\mathrm{pr}_ipri,剩下可能含有 pri\mathrm{pr}_ipri 的倍数的部分是 1×2×⋯⌊Npri⌋1 \times 2 \times \cdots \left \lfloor \frac{N}{\mathrm{pr}_i} \right \rfloor1×2×priN,变成类似的子问题。整理一下可得 αi=∑k=1∞⌊Nprik⌋\alpha_i = \sum_{k = 1}^{\infty}{\left \lfloor \frac{N}{\mathrm{pr}_i^k} \right \rfloor}αi=k=1prikN

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

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

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

预计得分:101010

算法二

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

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

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

空间复杂度:O(Tm)O(T m)O(Tm)

预计得分:353535

算法三

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

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

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

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

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

预计得分:65∼10065 \sim 10065100

算法四

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

更具体来说,令 (x1x2⋯xm)p(x_1 x_2 \cdots x_m)_{p}(x1x2xm)p 表示 ∑i=1mxipm−i\sum_{i = 1}^{m}{x_i p^{m - i}}i=1mxipmippp 进制下的数字,那么 NNNpri\mathrm{pr}_ipri 进制下的某个数位 v⋅prikv \cdot \mathrm{pr}_i^kvprikαi\alpha_iαi 的贡献将会是 (vv⋯v)pri(v v \cdots v)_{\mathrm{pr}_i}(vvv)pri (共 kkkvvv),因此可以确定第 kkk 个数位对 αi\alpha_iαi 的贡献,从而可以按照 pri\mathrm{pr}_ipri 进制下从高位到低位枚举的顺序贪心地找到一个最小的 NNN 满足 αi=ei\alpha_i = e_iαi=ei,取这些 NNN111 的最大值即可得到答案。

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

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

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

预计得分:100100100

T3.游戏

By CommonAnts,题解 By CommonAnts

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

算法一

大力手算,分类讨论。

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

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

预计得分:151515

算法二

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

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

时间复杂度:O(nq)O(nq)O(nq)

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

预计得分:424242

算法三

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

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

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

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

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

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

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

预计得分:222222,结合前述可得 646464

算法四

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

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

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

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

预计得分:100100100

T4.随机数列

By tangjz,题解 By tangjz

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

算法一

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

时间复杂度:O(R1R2)O(R_1 R_2)O(R1R2)

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

预计得分:101010

算法二

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

不妨设 ⌈XiXj+XjXi⌉=k\left \lceil \frac{X_i}{X_j} + \frac{X_j}{X_i} \right \rceil = kXjXi+XiXj=k,考虑枚举 kkk 来统计 (Xi,Xj)(X_i, X_j)(Xi,Xj) 的数量,从而得到答案。对于 Xi=pX_i = pXi=p 的情况,有 XiXj≤p\frac{X_i}{X_j} \leq pXjXipXjXi≤Cp\frac{X_j}{X_i} \leq \frac{C}{p}XiXjpC,直接枚举 XiX_iXikkk 是行不通的,但是如果有 Xi≤XjX_i \leq X_jXiXj,便可以将枚举 XiX_iXi 后枚举 kkk,统计 XjX_jXj 数量的问题做到 O(∑p=1CCp)=O(ClogC)O(\sum_{p = 1}^{C}{\frac{C}{p}}) = O(C \log C)O(p=1CpC)=O(ClogC) 的复杂度,而对于 Xi>XjX_i > X_jXi>Xj 的情况,则可以枚举 XjX_jXj 后枚举 kkk 再统计 XiX_iXi 的数量。

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

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

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

预计得分:303030

算法三

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

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

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

空间复杂度:O(C)O(C)O(C)

预计得分:60∼10060 \sim 10060100