hdu 5371 Hotaru’s problem (manacher,set维护)

题意:找出满足这样性质的最长子串:子串类似wbw的形式,w和b构成回文。

题解:对已每个位置,以他为中心的最长回文长度是可以用用manacher算出来的,设F(i)表示i为中心能的最长回文长度,然后会发现对于形如上述的子串第一个分界点a必定有F(a)/2>L(中间串的长度),并且对于第二个分界点b也必定有F(b)/2>L;那么可以归纳成:找到一个最大的x使得a[i]>=x && a[i+x] >=x

令i+x=d,那么上述式子会变换成 d <= i + a[i] && d <= i + a[d]

于是要找到一个最靠近i+a[i]的位置d来满足条件,为了使第二个式子必定成立那么a[d]>=a[i]是必须恒成立的,所以考虑将每个F(i)根据F(i)的值从大到小将下标放入set,然后每次二分找第一个小于等于i+a[i]的值,这个值必定小于等于i+a[d],因为从大到小放入了,所以必定有a[d]>=a[i]。

对于a[i]>=x && a[i-x]>=x的证明同上。

所以综上,将每个F(i)每次取出最大的对应的下标i放入set,然后二分查找最靠近i+a[i]和i-a[i]的值,然后更新。

网上很多解法,有暴力过的,至今无法相信,应该数据比较弱吧。YM能用线段树过次题大牛

 

LEAVE A COMMENT