UOJ Logo qingyu的博客

博客

UOJ Round #25 题解

2023-06-04 23:36:13 By qingyu

设计草图

idea, solution from he_____he, data from csy2005

算法一

我会暴力!

枚举所有的区间,暴力枚举每个 ? 的取值,检验其是否为合法的括号序列。

时间复杂度为 O(n2n),期望通过子任务 3,得到 15 分。

算法二

如果 S 中只含有 ?,那么任意一个长度为偶数的区间都是合法的!

通过计算,发现答案即为 n2n2

期望通过子任务 1,得到 5 分。结合算法一可以得到 20 分。

算法三

注意到,一个区间合法当且仅当以下条件满足:

  1. 区间长度为偶数
  2. 将所有 ? 替换为 ( 后,把 ( 当成 1,) 当成 -1,所有前缀和均大于等于 0
  3. 将所有 ? 替换为 ) 后,把 ) 当成 1,( 当成 -1,所有后缀和均大于等于 0

第二个条件相当于对每个 l,存在一个 pl 使得在 lrpl 成立。

第三个条件相当于对每个 r,存在一个 qr 使得在 qrlr 成立。

在预处理出 pi,qi 后,我们可以枚举 lrO(1) 进行判定。时间复杂度为 O(n2)

期望通过子任务 34,得到 30 分。结合算法二可以获得 35 分。

算法四

注意到上述问题是一个二维数点问题,我们可以使用排序后树状数组来解决,时间复杂度为 O(nlogn)

期望通过所有子任务,可以获得 100 分。

见贤思齐

idea, data, solution from ix35

算法一

暴力模拟每一轮的操作。

每一轮模拟的复杂度是 O(n) 的,我们可以将询问离线后按照时间顺序来处理所有询问,这样复杂度即为 O(nd+q)

期望通过子任务 12,得到 40 分。

算法二

ipi 连边,将形成一棵基环内向树。我们先考虑比较简单的情形——一棵有根树该怎么做:

假设根的权值一直不变(或者看成每次 +1 也行),将第 j 天黄昏时第 i 个工程师的技术水平是 f(i,j),那么我们有:

{f(i,0)=aif(i,j)=f(i,j1)+[f(i,j1)f(pi,j1)]

可以发现,对于某个 j 如果 f(i,j)=f(pi,j)f(i,j)=f(pi,j)+1,那么之后也会始终保持这种关系。为了更好发掘这种性质,我们对 f 进行一个平移,定义:

g(i,j)=f(i,j+depi)depi

其中 depi 表示 i 的深度,那么:

g(i,j)=g(pi,j)g(i,j+1)=g(pi,j+1)

证明是直接的。

于是我们可以用线段树维护 g(i,),它可以通过在 g(pi,) 的基础上修改一段前缀(修改成一个常数或一个公差为 1 的等差数列)得到,时间复杂度为 O((n+q)logV),其中 V 是最大时间。

可以通过子任务 3,得到额外的 20 分。结合算法一可以获得 60 分。

算法三

再考虑基环树怎么做。事实上我们只需如下观察:设第 i 天所有工程师的技术水平最小值为 mni,则这一天所有权值为 mni 的人一定会增长,从而第 i+1 天所有人的权值最小值就是 mni+1=mni+1

这告诉我们,最小值一定每天都在工作使得自己的水平增长,所以我们找到一个环上 ai 最小的人,然后断掉 ipi 之间的边并假设 f(i,j)=ai+j,然后当成树做即可。

时间复杂度为 O((n+q)logV),期望通过所有子任务,得到 100 分。

装配序列

idea, data, solution from Kubic

出题人原本给的题意是求前缀严格 LIS,不过后来似乎是为了方便写题目背景改成了前缀最小非严格 LDS 划分,显然两者是完全等价的。

算法一

直接拿出前 106 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

期望得分:5

算法二

可以发现如果 xn2,那么答案为 n

直接拿出前 n2 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

时间复杂度 O(n2logn+m)

期望得分:15

算法三

考虑 LIS 的一种贪心求法:维护一个递增序列 b。假设当前考虑的数是 x,找到最小的 y 满足 byx 并将 by 改为 x。如果不存在这样的 y 那么就在 b 的末尾插入一个 x

这个算法通常的实现是按照下标从小到大,每次考虑一个值。但本题中我们考虑按照值从小到大,每次考虑一个下标。

我们考虑维护出这个长度不超过 n 的序列,每次询问的答案即为序列中 x 的数的个数。这是因为这个序列可以看作是在维护 dp 数组的差分。

我们可以归纳地认为任何一个时刻每种数保留的都是一个前缀。设当前考虑到的值在排列中的下标为 x,下标为 i 的数保留了 ci 个。那么进行如下过程:

  • 初始 cx=0
  • 依次访问 (x,n] 中的每一个 i,如果 cx<ci,那么交换 cxci
  • 依次访问 [1,x) 中的每一个 i,如果 cx<ci1,那么先交换 cxci,然后 cxcx1,cici+1
  • 最后 cxcx+1

直接暴力维护即可做到 O(n2+mlogn)

期望得分:40

算法四

b=a1

我们相当于要将 b 分为 m 段,使得它们的 LIS 之和最大。

可以发现 LIS(bl,r+1)+LIS(bl+1,r)LIS(bl,r)+LIS(bl+1,r+1),即转移矩阵满足四边形不等式。因此答案关于 m 是下凸的。

因此我们可以使用 wqs 二分,设当前二分的斜率为 w

问题转化为:选出 b 的一个子序列 p,最大化 |p|w×i=1|p|1[pi>pi+1]。使用树状数组优化 dp 即可做到 O(nlogn)

因此总时间复杂度为 O(nlog2n)

当然,直接使用亚单位蒙日矩阵快速幂科技也可以做到相同的复杂度。

期望得分:20

算法五

通过打表等方式可以发现在 n=2×105 且数据随机的情况下 c 中非零位置个数大概有 k=900 个左右。猜测 k 可能是 O(n) 级别,暂时还没能给出其证明。

实时维护这些非零位置即可做到 O(n(k+logn)+mlogn)

期望得分:55

算法六

可以发现 i=1ncin

设一个阈值 Bi=1n[ci>B]nB

在上面的过程中,每次访问到的 ci 是严格单调递增的,

考虑上面的过程中第二步的维护方法。

我们对于 B 中的每一种数用一个 set 维护它们的出现位置,对于 >B 的数直接维护它们的出现位置。

先对于每一种数找到它们在 (x,n] 中的第一次出现的位置。显然如果某种数在 (x,n] 中的第一次出现没有被访问到,那么这种数一定没有被访问到。这样我们在 O(Blogn+nB) 的时间复杂度内筛选出了 O(B+nB) 个有用的位置,然后在 O(B+nB) 的时间复杂度内模拟上面的操作,最后在 O(Blogn+nB) 的时间复杂度内更新位置信息。

因此总时间复杂度为 O(nBlogn+n2B+mlogn),取 B=nlogn 时可以得到最优的 O(nnlogn+mlogn)

期望得分:100

算法六 +ε

by 127

我们可以进一步分析算法六的复杂度!

我们刚才直接将一次 set 操作的时间复杂度估计为 O(logn)。考虑使用更加精确的分析方法。取 B=n,设 di 表示 cj=i 的个数。

那么我们有 i=1Bi×din,而一次操作的时间复杂度可以估计为 i=1Blog(di+1)

考虑 i=1B(di+1),可以化为 i=1B(i×di+i)B!

而我们知道:

i=1B(i×di+i)n+B(B+1)22n

根据均值不等式可以得到:

i=1B(i×di+i)(2nB)B=(2B)B

因此时间复杂度可以估计为:

i=1Blog(2Bi)log(2B)+1Blog(2Bx)dx=O(B)

因此总时间复杂度为 O(nn+mlogn)

期望得分:100

bonus: interval query with O~(n1.5) time

tips: seaweeds method

by 127

评论

C 算法五: c 中非零位置个数 is always |LIS| of a (up to some values), so its distribution seems studied: https://arxiv.org/abs/math/9810105 (k2N. I haven't read the paper, I'd love to hear good intuitive explanation) C 算法六 +ε simpler proof: ilog2(di+1)ij[di2j]j2n/2j=O(n)

发表评论

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