设计草图
idea, solution from he_____he, data from csy2005
算法一
我会暴力!
枚举所有的区间,暴力枚举每个 ?
的取值,检验其是否为合法的括号序列。
时间复杂度为
算法二
如果 ?
,那么任意一个长度为偶数的区间都是合法的!
通过计算,发现答案即为
期望通过子任务
算法三
注意到,一个区间合法当且仅当以下条件满足:
- 区间长度为偶数
- 将所有 ? 替换为 ( 后,把 ( 当成 1,) 当成 -1,所有前缀和均大于等于 0
- 将所有 ? 替换为 ) 后,把 ) 当成 1,( 当成 -1,所有后缀和均大于等于 0
第二个条件相当于对每个
第三个条件相当于对每个
在预处理出
期望通过子任务
算法四
注意到上述问题是一个二维数点问题,我们可以使用排序后树状数组来解决,时间复杂度为
期望通过所有子任务,可以获得
见贤思齐
idea, data, solution from ix35
算法一
暴力模拟每一轮的操作。
每一轮模拟的复杂度是
期望通过子任务
算法二
从
假设根的权值一直不变(或者看成每次
可以发现,对于某个
其中
证明是直接的。
于是我们可以用线段树维护
可以通过子任务
算法三
再考虑基环树怎么做。事实上我们只需如下观察:设第
这告诉我们,最小值一定每天都在工作使得自己的水平增长,所以我们找到一个环上
时间复杂度为
装配序列
idea, data, solution from Kubic
出题人原本给的题意是求前缀严格 LIS,不过后来似乎是为了方便写题目背景改成了前缀最小非严格 LDS 划分,显然两者是完全等价的。
算法一
直接拿出前
期望得分:
算法二
可以发现如果
直接拿出前
时间复杂度
期望得分:
算法三
考虑 LIS 的一种贪心求法:维护一个递增序列
这个算法通常的实现是按照下标从小到大,每次考虑一个值。但本题中我们考虑按照值从小到大,每次考虑一个下标。
我们考虑维护出这个长度不超过
我们可以归纳地认为任何一个时刻每种数保留的都是一个前缀。设当前考虑到的值在排列中的下标为
- 初始
。 - 依次访问
中的每一个 ,如果 ,那么交换 和 。 - 依次访问
中的每一个 ,如果 ,那么先交换 和 ,然后 。 - 最后
。
直接暴力维护即可做到
期望得分:
算法四
设
我们相当于要将
可以发现
因此我们可以使用 wqs 二分,设当前二分的斜率为
问题转化为:选出
因此总时间复杂度为
当然,直接使用亚单位蒙日矩阵快速幂科技也可以做到相同的复杂度。
期望得分:
算法五
通过打表等方式可以发现在
实时维护这些非零位置即可做到
期望得分:
算法六
可以发现
设一个阈值
在上面的过程中,每次访问到的
考虑上面的过程中第二步的维护方法。
我们对于
先对于每一种数找到它们在
因此总时间复杂度为
期望得分:
算法六
by 127
我们可以进一步分析算法六的复杂度!
我们刚才直接将一次 set 操作的时间复杂度估计为
那么我们有
考虑
而我们知道:
根据均值不等式可以得到:
因此时间复杂度可以估计为:
因此总时间复杂度为
期望得分:
bonus: interval query with
tips: seaweeds method
by 127