抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

题面 洛谷P4197 Solution 这题的确是可以用库鲁斯卡尔重构树+主席树来搞,但是本蒟蒻太菜了并不会,因此只能给大家讲讲离线+splay启发式合并的搞法。 首先,我们考虑把询问离线下来并按限制从小到大排序。然后我们可以考虑把边一条一条插入到图里面去,直到某个询问的限制。这样子,问题就变为了询问某一个连通块的K小值,连通块可以合并。 这个问题就肥肠简单了,我们可以用各种各样的数据结构...

题面 洛谷P3302 Solution 拿到这道题,我们不妨先想一下静态的树上K大怎么搞。 静态树上K大有两种办法,一是树链剖分+平衡树,二是主席树做链前缀和。前者的复杂度是$O(log^2n)$的,而后者只有$O(logn)$。 我们考虑把数字全部离散化,然后开权值主席树,每颗主席树记录从它出发到根的路上每个数字出现了多少个。接下来,我们只需要找到LCA。因为数字出现个数满足可减性,因此...

题面 传送门:SPOJ 694 Solution 这题可以用SAM来搞,也可以用SA来搞。但无论是哪种搞法,都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先,我们先把SAM建出来。根据SAM的性质,我们从出发点随着SAM任意走,走到哪里都是一个完全不同的子串。因此,我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出...

题面 洛谷 P2743 Solution 这题可以用哈希做,也可以用SA做。下面我们分别讲一下两种做法。 哈希 首先,我们把转掉的问题处理掉。我们考虑把原串做差分数组,即用后面那一个减去前面那一个。这样子,我们直接在新的串上找完全相同的两个不可重叠子串即可。 这个,我们考虑先在外面二分一个答案的长度,然后暴力做,从后往前扫,把所有子串都丢到哈希表里面,插入一个新的串之前,就检查一下之前是否...

题面 传送门:洛谷P2852 Solution 首先,我们阅读题面可以发现题目让我们求出一个出现次数>k的可重复的子串。 这玩意我们可以用SA求,也可以用SAM求。 SA 这题用SA做就比较妙,首先我们显然要求把SA及height求出来。 因为两个后缀的LCP是它们之间的height的min,我们可以利用这个性质。 考虑一个子串,它所能“控制”的区间的所有的height都必须比它大。...

为什么要学后缀数组 为了解决一类字符串神题妙题。 什么是后缀数组 什么是后缀 要理解什么是后缀数组,首先要明白什么是后缀。 一个字符串$[S_1:S_n]$的后缀为:$[S_i:S_n],i∈[1,n]$ 用人话来说,就是从每个字符开始到这个字符串的结尾所组成的串均为这个字符串的后缀。 例如: 假设我现在有一个字符串“abaaba”,那么。她的后缀有:a,ba,aba,aaba,baaba...

什么是基数排序 基数排序是一个时间复杂度为:$O(n*MAXNUM/base)$,空间复杂度为$O(base+n)$的优秀排序算法。 基数排序有什么用 我们知道,桶排序可以在$O(MAXNUM)$的时间内,$O(MAXNUM)$的空间内排序一个数组,快速排序可以在$O(nlogn)$的时间内,$O(n)$的空间内排序一个数组。 如果有一个排序任务的最大数字比桶大,而数字数量又爆多怎么办?这时...

为什么要学左偏树 有时候,某些题目要求我们合并两个堆。 合并两个堆,大家都知道可以用splay暴力启发式合并处理。很不幸的是,这玩意的复杂度是$O(nlog^2n)$的,在一些毒瘤题目专门考可并堆的题目中,是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法,她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面...

题面 洛咕 Solution 题目要求求出区间众数,强制在线。 区间众数是一个比较尴尬的问题,我们无法用区间数据结构来处理这个问题,因为我们没法很好的合并区间众数的答案。 既然区间数据结构解决不了这个问题,我们可以考虑一下使用基于分块的算法,例如莫队。 这题用莫队非常好处理,不幸的是,这题要求强制在线。 因此我们考虑使用分块算法。 分块算法的核心在于把一整个块的信息压缩起来以便快速处理。 ...

题面 传送门:洛咕 Solution 调到自闭,我好菜啊 为了方便讨论,以下式子$m>=n$ 为了方便书写,以下式子中的除号均为向下取整 我们来颓柿子吧qwq 显然,题目让我们求: $\large \sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$ $lcm$没法玩,我们转到$gcd$形式: $\large \sum_{i=1}^n\sum_{j=1}^m \fra...