F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1414 >> 沙茶求解此题做法
maxSX @ 2012-02-15 18:56:10
[ Quote ] [ Edit ] [ Delete ] 1#
RT,承认被虐,没有想法
dnc1994 @ 2012-02-16 16:33:53
[ Quote ] [ Edit ] [ Delete ] 2#
对称的正方形
这题的大致思路是这样的:枚举正方形的对称轴,找到以它为对称轴的最大的对称正方
形时多大。首先我们需要预处理2 个东西:h[i][j],s[i][j]。h[i][j]表示以第i 行第j 个对称轴
为对称轴的最长回文串有多长,同理设s[i][j]。通过类似于扩展KMP 的方法,我们可以在
O(n2)的时间做好预处理。对于每个对称轴,我们分别计算它们向左向右向上向下能扩展多
长,再取其中较小者为以该对称轴为对称轴的最大的对称正方形的大小。以计算向左扩展长
度的为例:我们从左往右扫描,设si 表示第i 个对称轴向左最大扩展到哪里,则对于i≤j
为,我们有si≤sj。我们再通过维护一个队列就知道当前的s 到i 的最小值。这样我们就
可以在O(n2)的时间内计算除向左扩展的长度,同理可以计算其它。最终本算法的复杂度为
O(n2)
kac @ 2012-02-16 16:56:11
[ Quote ] [ Edit ] [ Delete ] 3#
Manacher+单调队列
maxSX @ 2012-02-16 19:28:08
[ Quote ] [ Edit ] [ Delete ] 4#
的确,神算法,膜拜
littlered @ 2018-06-23 23:35:56
[ Quote ] [ Edit ] [ Delete ] 5#
膜拜膜拜 , 比网上的题解好
[Top] [Previous Page] [Next Page]

HOME Back