暑假训练round2 D: 好序列（Manacher）

Problem 1061: 好序列

Time Limits:  1000 MS   Memory Limits:  65536 KB

64-bit interger IO format:  %lld   Java class name:  Main

Description

杨神觉得好的序列需要符合这两个条件
1.这段序列可以平均分成三段，第一段和第三段相同
2.第二段与第一段相反
给你一个由n个非负整数组成的序列，问连续子序列是好序列时，该连续子序列的长度是多少。

Input

第一行为t 代表t组测试数据
第二行为n ( 1 <= n <= 100000)代表序列由n个非负整数组成
第三行为n个数 (ai < 100000)

 

Output

开始为"Case #i: " 后面跟着一个整数，代表最长的连续子序列为好序列的长度

Sample Input

1
10
2 3 4 4 3 2 2 3 4 4

Output for Sample Input

Case #1: 9

比赛的时候只知道用manacher，之后就感觉下标处理起来麻烦就没做了……，正确解法是枚举i的对称点i+p[i]-1,再从对称点再往回扫一遍，看看存不存在也能往回覆盖至i点，有的话就记录[当前点-i]为1.5段的长度即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=100010;
int arr[N],p[N*2];
int s[N*2];
int n;
void manacher()
{
	MM(p,0);
	MM(s,0);
	int i, len=0;
	s[len++]=-2;
	s[len++]=-1;
	for (i=0; i<n; i++)
	{
		s[len++]=arr[i];
		s[len++]=-1;
	}
	int mx=0, idd=0;
	for (i=0; i<len; i++)
	{
		if(mx>i)
			p[i]=min(p[2*idd-i],mx-i);
		else
			p[i]=1;
		while (s[i+p[i]]==s[i-p[i]])
			p[i]++;
		if(i+p[i]>mx)
		{
			mx=p[i]+i;
			idd=i;
		}
	}
}
int main(void)
{
	int tcase, i, j, cnt=0;
	scanf("%d",&tcase);
	while (tcase--)
	{
		MM(arr,0);
		scanf("%d",&n);
		for (i=0; i<n; i++)
			scanf("%d",&arr[i]);
		manacher();
		int ans=0;
		for (i=1; i<2*n+2; i+=2)
		{
			for (j=i+p[i]-1; j-i>ans; j-=2)//往回遍历
			{
				if(j-(p[j]-1)<=i)
				{
					if(j-i>ans)
					{
						ans=j-i;
						break;
					}
				}	
			}
		}					
		printf("Case #%d: %d
",++cnt,3*(ans>>1));
	}
	return 0;
}