[ZOJ 3199 Longest Repeated Substring] 分治、扩展KMP

链接

给定一串S,令S = *xx* (其中*为通配符)
问这个x最长的长度能是多少。

以前用罗穗骞论文的方法按后缀数组枚举长度做的。但是那个需要ST表,空间是O(n lg n)。最近从叉姐那里学会了新姿势,可以用分治的思想做,只要O(n)的空间。

具体想法是每次把字符串分成两半,分别算两边的答案。

对于跨越中间边界的,设中点为S_{mid},那么枚举答案的长度L,然后因为他跨越边界,那么一定包含S_{mid}
因为答案长度为L,那么要么S_{mid + L}在答案中,要么S_{mid - L}在答案中。

不失一般性假设S_{mid + L}在答案中,那么肯定存在一段S_{i..i+L-1} = S_{j..j+L-1},其中i \leq mid \leq i + L - 1, j \leq mid + L \leq j + L - 1

显然S_{i..i+L-1}就是我们要求的目标串。

再观察一下,会发现这个条件等价于lcp(mid, mid+L) + revlcp(mid, mid + L) - 1 \geq L
其中revlcp是指往前的lcp

最终发现,对于跨越的情况,我们只要求得lcp(mid, x)和revlcp(mid, x)的函数值即可。而这个显然可以通过拓展KMP处理出来,具体做法就是令T = S_{mid .. n} + S_{1..n},对T求拓展KMP,再对边界取一下min,反的可以转化成正的求解。

至此,这题得到了解决。
时间复杂度O(n lg n)。
空间复杂度O(n)。

代码:https://gist.github.com/edwardmjm/2b88d649ced1d7ce9a99

大酒神浙大演讲观后感

地址
昨晚翻出酒神的演讲从头到尾听完了。虽然镜头很抖,酒神确实也不怎么精于演讲,但还是发现了很多有共鸣的地方。
“我是一个很注重结果的人”
“我去打比赛就是为了以后有事情可以吹牛”
“对不起,这场比赛我要赢”
“如果你觉得失败就像砍掉你一条腿一样,你肯定是无敌的”
“一个人的成功在于不断地经营自己的优势”
“成功的人总是盲目自信的”
“我也试过很多次组队,也失败过很多次”
“我觉得我就应该打中路solo”
“一开始我想着自己怎么打就行了”
“我开始观察队友在干什么”
……

静态KD树通用模板

今天在opencup上遇到了一个三维区间询问的题。

虽然知道KD树可以做,自己对于二维的也随便写。但是三维的就没怎么写过了。

于是今天下决心写了一个静态KD树的通用模板。于是就有了这个东西。

KD树还是很强大的,还能做一些二维线段树不能做的东西。在想不到比较优美的做法的时候,直接上KD树往往能轻松AC。

模板链接:https://gist.github.com/edwardmjm/11118130

Andrew Stankevich Contest #32 Problem C 二维平面反演, 动态凸包

地址

给定n(1 ≤ n ≤ 105)个点,一个点(x, y)是好的,当且仅当以(0, 0) - (x, y)为直径的圆内不包含其它好的点。(x, y)皆是原点外的整点。0 ≤ |x|, |y| ≤ 30000。输出所有好的点。

因为题目的这个递归定义,显然应该按(x, y)到原点的距离从小到大排序,然后每次插入点之前检测一下,如果圆内没有点就插入,否则就拒绝。

这题因为给的都是整点,范围又小,构造不出大数据,直接用这个方法是能过的- -b……但是显然这不是一个令人满意的做法。

因为所有的圆都过原点,很容易想到对整个平面进行反演

这样圆都会变成一条直线,而“在圆内”反演后就会变成“在这个直线的一侧”(与原点相反的一侧)。

于是反演过后变成这样一个问题:每次给一条直线,问是否之前插入的点都在这个直线的某一侧。如果是,把这个点插入点集。

那么如何快速判断一个点集是否全都在一条直线的某一侧?

不妨把直线看成一个向量,容易想到如果对这些点集求出一个凸包,那么凸包上向量的极角是单调的,在上面找到出与当前直线对应向量最相近的两条边,中间的那个顶点就是在该直线法向量方向看最远的点。于是只要判断这个点是否符合条件就可以了。

剩下的问题就是给定一个凸包,每次有插入操作,怎么快速动态地维护这个凸包?

对于这个单调的东西,手写一个平衡树维护凸包顶点肯定是能做的,但是也可以偷懒利用STL的set。但是这里有个问题,到底是维护set < Line > set < Point >?对于判断是否在直线一端的部分,只有存Line能做,对于后面凸包的动态插入,只有Point能做……于是只能两个都维护了,在插入凸包的时候两个一起操作。

这里还有一个小技巧,因为叉乘只能判左还是右,超过180°的很容易写出奇怪的情况,于是动态凸包我是通过上凸壳和下凸壳来维护的。但是这样就要写两种情况,一个好的方法是对于下凸壳,直接左右翻转,上下翻转(也就是所有点的坐标都取负),这样就变成同样维护上凸壳了。

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

PS.反演精度比较坑爹,建议使用相对误差进行几何上的判定。

代码

Codeforces #239

A

把直角的那个顶点放在原点,枚举其中一条边的横坐标,然后勾股定理得到纵坐标。旋转90度得到另外一个直角边的方向向量,伸缩到对应长度,看看是否整点。唯一的trick是除了直角边的那条边平行与坐标轴要注意。

B

令f[i][j]表示现在才在i上,i上的次数是奇数,其它位置都是偶数的情况下,从i走到j所需要的步数。
f[i][j] = f[i][j-1] + f[a[j-1]][j-1] + 2
记忆化递归求解f[0][n]即可。

C

先考虑单次操作的情况,f[i][0] = C[k + i - L][k] = 要求的答案。
对这个f[i][0]做一次差分,那么f[i][1] = f[i + 1][0] - f[i][0],可以看做这是i处的导数。
然后f[i][2]视为对f[i][1]这个数列作差分,一直往上。
然后由于C[m][n] = C[m - 1][n] + C[m - 1][n - 1],所以你会发现f[i][j] = C[k + i - L][k - j]。
那么现在变换一下f的递推关系得到f[i + 1][j] = f[i][j] + f[i][j + 1]。
也就是说,如果我知道到第i个数字的各阶导数,那么我可以一个一个数字往后推,得到其它数字以及他们的各阶导数。
又因为f[i][j] = C[k + i - L][k - j],k不超过100,所以j只要算到100阶就行了,再高后面的都是0。
由于这个递推式里面是加法,和答案里的求和相吻合,所有可以把各个询问叠在一起往后加着算。

于是得到这么一个算法,对于每个询问,求出他在l处的各阶导数,放进f[l][0..k]里面,在r出也求出各阶导数,放到f[r][0..k]里面(这里是为了抵消,用减法放进去)。
最后,大家一起从前往后推就好了。

D

令f[i][j][k]表示第i行到第j行这个子矩阵里,左边界选择第k列,右边界最远能到第几列。
首先f[i][j][k] ≤ min(f[i][j - 1][k], f[i + 1][j][k], f[i][j][k + 1])
除了这几个限制外,可能产生新冲突的就只可能是"第i行k列和第j行k列上的元素"与"第i行后面的元素和第j列后面的元素"。
那么按j - i的大小枚举i, j,再倒着枚举k,就可以用一个桶记录每个元素在第i行以及第j行最前出现的列是多少。
这样就可以处理掉这两个元素产生的冲突。
桶的清空稍微用一些编码技巧,就能O(n^3)写过去。