竞赛讨论区 > 【题解】牛客练习赛70
头像
Atoner
编辑于 2020-09-27 11:42
+ 关注

【题解】牛客练习赛70

重新排列

一段字符串可以重新排列成喜欢的子串当且仅当“puleyaknoi”中每个字母在其中出现至少一次,考虑用双指针,当找到符合条件的右端点,更新答案,然后将左端点向右移动直到不符合要求,重复如上操作直至结束。复杂度
sol

拼凑

因为不能重新排列顺序,所以要求必须是按顺序出现。考虑用基础DP,表示到第i个位置,匹配到模板串第j位的最优答案。因为模式串里没有重复字符,所以转移十分容易。如果当前位置与模式串里的第k位相同,可以从转移过来,任何情况下都可以从继承答案,复杂度
sol

Mu函数

发现一个事情,总共有两种情况:

1.进入一个1,-1交替的循环

2.

因为4的倍数都是0,所以有用的操作最多就4次。于是K的范围便没了太大意义。

所以剩下的部分就是快速求莫比乌斯函数了,线性筛和质因数分解均可解决问题。

质因数分解如果写的比较暴力大概率会过不去。

复杂度

sol

数树

有个经典结论是树的,这对森林里每棵大小大于1的树都是成立的。所以问题只剩下维护是否有边和是否连的是重边,是否删除的是不存在的边。本质上都是维护边,开一个map存储一下即可。每次计算答案用度数大于1的点的数量减去图上的边的数量。时间复杂度

实际上这题可以用LCT通过,但在代码量上复杂了些。

sol

看比赛

考虑题意,有一个简单的转化:有一些长为1的不同线段,对于每个线段,选择其左端点或右端点做为关键字进行排序,求不同序列的个数。

首先我们按照左端点排序,左端点相同的按线段编号优先级,以下表示排序后的线段编号区间

定义线段前缀选择端点的两种方案是不可区分的,当且仅当后缀无论使用任何选法,都不能区别开这两种取法。

表示可区分的方案数,不考虑不可区分的状态,应有。考虑容斥掉不可区分的部分。

对于线段 ,容易发现,在按线段左端点排好序的前提下,可以找到一个,使得j的右端点距离i的左端点最近。也可以找到使得的左端点离着的右端点最近。

那么线段前缀全部取左端点,全部取右端点,这样对于的键值取法既不可区分。

容易理解的,对于线段的两种取法,对线段处的额外贡献了不可区分的f的方案,所以减去。可以证明这样的算法对于是不重不漏的。

由于单调,动态规划部分复杂度为线性。所以复杂度为排序复杂度。实现非常简单,建议离散化降低特判难度。

sol

曲调

首先前缀和,然后变成求区间内求绝对值最小的两个数的差。设前缀和数组为 .

考虑离线,将询问按右端点排序。我们从小到大枚举询问区间的右端点 , 同时用数据结构维护每个左端点的答案。考虑新增一个数 与它前面的点构成数对产生的贡献。

这里我们只考虑 组成数对的贡献, 对于 的情况反过来按同样的方法处理一遍即可。

首先我们找到最大的 满足 ,记为 ,那么对于所有 ,左端点为 的询问都要与 。然后我们找到最大的 满足 ,记为 ,那么对于所有 ,左端点为 的询问都要与 。就这样依次找下去,每次更新答案,直到 为止。

问题是,最坏情况下每个点寻找 的次数可能达到 级别。

观察到这样一个性质:当我们寻找 时,若 , 那么数对 对答案没有任何贡献,因为无论询问的区间是什么, 总比 优。于是我们可以只寻找那些 的最大的 作为 ; 后面的也照此方法优化,每次只查询介于上一次找到的数和 之间的最靠右的点。这样每次的查询值域区间 都不超过上一次的一半,总共只会有 次寻找 . (数组的值域)

寻找 可以用主席树简单维护来做到单次 ; 区间取 也可以用线段树等数据结构简单维护。

时间复杂度 .

sol

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐