HDU-5371 Manacher+线段树维护

最新推荐文章于 2025-05-31 16:10:35 发布

AC_Machine

最新推荐文章于 2025-05-31 16:10:35 发布

阅读量474

点赞数

分类专栏：字符串-Manacher 数据结构-线段树文章标签： ACM java 字符串 Manacher

本文链接：https://blog.csdn.net/AC_Machine/article/details/52172139

版权

字符串-Manacher 同时被 2 个专栏收录

3 篇文章

订阅专栏

数据结构-线段树

3 篇文章

订阅专栏

Hotaru's problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3123 Accepted Submission(s): 1057

Problem Description

Hotaru Ichijou recently is addicated to math problems. Now she is playing with N-sequence.
Let's define N-sequence, which is composed with three parts and satisfied with the following condition:
1. the first part is the same as the thrid part,
2. the first part and the second part are symmetrical.
for example, the sequence 2,3,4,4,3,2,2,3,4 is a N-sequence, which the first part 2,3,4 is the same as the thrid part 2,3,4, the first part 2,3,4 and the second part 4,3,2 are symmetrical.

Give you n positive intergers, your task is to find the largest continuous sub-sequence, which is N-sequence.

Input

There are multiple test cases. The first line of input contains an integer T（T<=20）, indicating the number of test cases.

For each test case:

the first line of input contains a positive integer N（1<=N<=100000）, the length of a given sequence

the second line includes N non-negative integers ,each interger is no larger than

109 , descripting a sequence.

Output

Each case contains only one line. Each line should start with “Case #i: ”,with i implying the case number, followed by a integer, the largest length of N-sequence.

We guarantee that the sum of all answers is less than 800000.

Sample Input

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

Sample Output

  
  
   
   Case #1: 9

Author

UESTC

Source

2015 Multi-University Training Contest 7

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5371

题目大意：

定义一种N-sequence，由三部分组成，第一部分与第二部分对称，第一部分与第三部分相同。给出一个n个数的序列，问其中最长的N-sequence的长度。

解题思路：

Manacher预处理，若有以i为中心的回文串s1和以j为中心的回文串s2，且s1的右半部分覆盖了j，s2的左半部分覆盖了i，那么可形成一个长度为(j-i)/2*3的N-sequence。从左到右枚举i，每次查询[i-pp[i]+1,i]中到i最远的被标记的中心位置，然后将位置i标记，到位置i+pp[i]-1处再将标记i去掉，查询与更新标记用线段树实现即可。

AC代码：

import java.io.*;
import java.util.*;

public class Main {
	static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static int nextInt() throws IOException    
	{  
	    in.nextToken();    
	    return (int)in.nval;     
	}
	static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
	static int T,n,len,inf=(int)1e9+7;
	static int ans,res,ee;
	static int[] aa=new int[100005];
	static int[] ss=new int[200005];
	static int[] pp=new int[200005];
	static int[] min=new int[800005];
	static int[] head=new int[200005];
	static int[] next=new int[200005];
	static int[] edge=new int[200005];
	static void add(int a,int b)
	{
		edge[ee]=b;next[ee]=head[a];
		head[a]=ee++;
	}
	static void updata(int a,int k,int l,int r,int x)
	{
		if(l==r) { min[k]=x;return;}
		int mid=(l+r)/2;
		if(a<=mid) updata(a,k*2+1,l,mid,x);
		else updata(a,k*2+2,mid+1,r,x);
		min[k]=Math.min(min[k*2+1],min[k*2+2]);
	}
	static int query(int a,int b,int k,int l,int r)
	{
		if(a>r||b<l) return inf;
		if(a<=l&&r<=b) return min[k];
		int mid=(l+r)/2;
		int vl=query(a,b,k*2+1,l,mid);
		int vr=query(a,b,k*2+2,mid+1,r);
		return Math.min(vl,vr);
	}
	static void Manacher()
	{
		Arrays.fill(ss,-1);
		for(int i=1;i<=n;i++)
			ss[i*2]=aa[i];
		ss[0]=-2;len=n*2+1;
		int max=0,id=0;
		for(int i=1;i<=len;i++)
		{
			if(max>i)
				pp[i]=Math.min(max-i,pp[id*2-i]);
			else pp[i]=1;
			while(ss[i+pp[i]]==ss[i-pp[i]])
				pp[i]++;
			if(i+pp[i]>max) { max=i+pp[i];id=i;}
		}
	}

	public static void main(String[] args) throws IOException {
		//Scanner in=new Scanner(System.in);
		T=nextInt();
		for(int t=1;t<=T;t++)
		{
			n=nextInt();
			for(int i=1;i<=n;i++)
				aa[i]=nextInt();
			Manacher();ans=0;
			Arrays.fill(min,inf);
			Arrays.fill(head,-1);ee=0;
			for(int i=1;i<=len;i+=2)
			{
				res=query(i-pp[i]+1,i,0,1,len);
				ans=Math.max(ans,i-res+1);
				updata(i,0,1,len,i);
				add(i+pp[i]-1,i);
				for(int j=head[i];j!=-1;j=next[j])
					updata(edge[j],0,1,len,inf);
			}
			ans=ans/2*3;
			out.println("Case #"+t+": "+ans);
		}
		out.flush();
	}
}