bzoj 2342 双倍回文

Set+二分

　　题目链接：bzoj 2342

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：这道题是让我们求一个双倍回文串。显然一个双倍回文串也是一个回文串，只不过在此基础上它的左部（或者右部）也是一个回文串罢了。所以我们是要求出一个最长的回文串使得这个回文串的左半边也是一个回文串。我们将双倍回文的那个回文串对应的极长回文串称为X，将双倍回文串的左半部分的那个回文串称为Y，然后我们考虑一下这两个串的回文中心的位置关系。首先我们发现Y的长度是≤X长度的一半的，所以Y串的中心是≥X串左半部分的中心的。然后我们考虑Y串所对应的那个极长的回文串，我们发现它的右端点一定是≥X串的中心。所以我们自然的想到了一种做法：我们从大到小枚举那个双倍回文串的中心x，然后我们把所有的 i+len[i] ≥ x的回文串的中心点加入到一个 S e t 中去，然后我们只需要在这个 S e t 中二分出第一个 ≥ (x-len[x]/2)的中心点，就可以求出以x为中心的最长双倍回文串的长度了。

　　我思故我在：冷静分析、罗列题目中所给的条件和条件之间的关系。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
struct table{
	int id,val;
}stack[500500];
char ap[500500];
char map[500500*3];
int len[500500*3];
set<int> s;
inline int max(int a,int b)
{
	return a > b ? a : b ;
}
bool cmp(table a,table b)
{
	return a.val>b.val;
}
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",ap+1);
	for(int i=1;i<=n;i++)
	{
		map[i*2-1]='*';
		map[i*2]=ap[i];
	}
	map[n*2+1]='*';
	len[1]=0;
	int now=1;
	for(int i=2;i<=n*2+1;i++)
	{
		if(i<=now+len[now])
		{
			int x=now-(i-now);
			if(x-len[x]>now-len[now]) len[i]=len[x];
			else
			{
				int j=now+len[now]-i+1;
				while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) j++;
				now=i,len[i]=j-1;
			}
		}
		else
		{
			int j=1;
			while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) j++;
			now=i,len[i]=j-1;
		}
	}
	for(int i=1;i<=n*2+1;i+=2)
	{
		stack[(i+1)/2].id=i;
		stack[(i+1)/2].val=i+len[i];
	}
	sort(stack+1,stack+1+n+1,cmp);
	int tail=1;
	int ans=-1;
	for(int i=n*2+1;i>=1;i-=2)
	{
		while(stack[tail].val>=i) s.insert(stack[tail].id),tail++;
		int x=i-len[i]/2;
		int y=*s.lower_bound(x);
		int z=max(i-y,0)*2;
		ans=max(ans,z);
	}
	cout<<ans<<endl;
	return 0;
}