本文主要是介绍hdu5371（2015多校7）--Hotaru's problem（Manacher+线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：定义一个子串，子串由三部分组成，其中第一部分和第三部分相同，第一部分和第二部分对称。给出一个n个数的序列，问序列中最长的符合要求的子串的长度。
例如2 3 4 4 3 2 2 3 4，第一部分2 3 4，第二部分4 3 2 ，第三部分2 3 4，符合条件。
题目的大意可以转化成求两个回文串，其中第一个回文串的右侧和第二个回文串的左侧重叠。
首先使用Manacher算法，求出以每一个位置为中心的最长回文串，如果不知道Manacher，看点击打开链接
计算完所有的最长回文串的长度后，枚举第一部分和第二部分的断点，也就是枚举以每一个位置i为中心的回文串s1，如果存在符合条件的子串，那么第二部分和第三部分的断点j，就应该在回文串s1的右侧，并且断点位置形成的回文串s2的左边界会小于或等于i。
用线段树维护符合条件的值，当枚举到i位置的时候，如果回文串s的左边界小于等于i，那么就把s的对称位置加入线段树，当回文串的对称位置小于i后，就把该对称位置去掉，对于i来说，以i为中心的回文串为[l,r]，那么线段树中[i+1,r]范围内的数都是满足条件的，找出最大值。然后继续遍历i，最终得到最长的子串。
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
#include <algorithm>
using namespace std ;
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL __int64
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define maxn 310000
int p[maxn] ;
int s[maxn] , str[maxn] ;
int cl[maxn<<2] ;
vector <int> vec[maxn] ;
int init(int l) {int i = 0 , j = 0 ;str[j++] = -2 ;while( i < l ) {str[j++] = -1 ;str[j++] = s[i] ;i++ ;}str[j++] = -1 ;str[j] = -3 ;return j ;
}
void Manacer(int l) {int i , max1 = 0 , id ;for(i = 1 ; i < l ; i++) {if( max1 > i )p[i] = min(p[2*id-i],max1-i) ;elsep[i] = 1 ;while( str[i-p[i]] == str[i+p[i]] )p[i]++ ;if( p[i]+i > max1) {max1 = p[i] + i ;id = i ;}}
}
void push_up(int rt) {cl[rt] = max(cl[rt<<1],cl[rt<<1|1]) ;
}
void update(int i,int k,int l,int r,int rt) {if( l == r ) {if( k ) cl[rt] = i ;else cl[rt] = 0 ;return ;}int mid = (l+r)/2 ;if( i <= mid ) update(i,k,l,mid,rt<<1) ;else update(i,k,mid+1,r,rt<<1|1) ;push_up(rt) ;
}
int query(int ll,int rr,int l,int r,int rt) {if( ll > rr || ll > r || rr < l ) return -1 ;if( ll <= l && rr >= r ) return cl[rt] ;int mid = (l+r)/2 ;return max( query(ll,rr,l,mid,rt<<1) , query(ll,rr,mid+1,r,rt<<1|1) ) ;
}
int main() {int t , step = 0 ;int i , j , n , m , l , k , max1 ;scanf("%d", &t) ;while( t-- ) {scanf("%d", &n) ;for(i = 0 ; i < n ; i++)scanf("%d", &s[i]) ;l = init(n) ;Manacer(l) ;for(i = 0 ; i < l ; i++)vec[i].clear() ;for(i = 1 ; i < l ; i += 2 ) {vec[ i-p[i]+1 ].push_back(i) ;}memset(cl,-1,sizeof(cl)) ;max1 = -1 ;for(i = 1 ; i < l ; i += 2) {m = vec[i].size() ;for(j = 0 ; j < m ; j++)update(vec[i][j],1,1,l,1) ;update(i,0,1,l,1) ;k = query(i+1,i+p[i]-1,1,l,1) ;max1 = max(max1,(k-i)/2*3) ;}if( max1 == -1 ) max1 = 0 ;printf("Case #%d: %d\n", ++step, max1) ;}return 0 ;
}这篇关于hdu5371（2015多校7）--Hotaru's problem（Manacher+线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
