BZOJ 2084 Antisymmetry

发表于 | 更新于

Link

Solution

反对称串长度一定为偶数 反对称串反掉一半之后一定是回文串 于是就试着求一下每个点左边的串反转之后，这个点的回文半径 回文串？于是考虑Manacher Manacher的主要条件是 A回文，B回文，那么C回文 现在考虑一下能不能直接套 A[1:A.length()2]RA[A.length()+12:A.length()]A[1:\dfrac {A.length()}2]^RA[\dfrac {A.length()+1}2:A.length()]回文 B[1:B.length()2]RB[B.length()+12:B.length()]B[1:\dfrac {B.length()}2]^RB[\dfrac {B.length()+1}2:B.length()]回文 是可以得到右边的CC回文的 所以直接套Manacher即可，每次把真字符取反；在分隔符处更新maxRight，统计答案。 至于为什么在分隔符处更新maxRight我也不知道，，只是如果每次都更新确实会多算一些不合法的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include "lucida"
using std::min;
const int MAXN=500000+11;
int64 Manacher(int s[],int n) {
	static int ms[MAXN<<1]={-2},rad[MAXN<<1];
	for(int i=1;i<=n;++i) {
		ms[(i<<1)-1]=-1;
		ms[i<<1]=s[i];
	}
	ms[++(n<<=1)]=-1;ms[n+1]=-3;s=ms;
	int mxr=0,mxp=0;int64 res=0;
	for(int i=1;i<=n;++i) {
		rad[i]=i<=mxr+mxp-1?min(mxp+mxr-i,rad[2*mxp-i]):1;
		while(s[i-rad[i]]==s[i+rad[i]]) 
			rad[i]++;
		if(i+rad[i]>mxp+mxr && s[i]<0) {
			mxp=i;
			mxr=rad[i];
		}
		s[i]^=s[i]>=0;
		res+=((rad[i]-1)>>1)*(s[i]<0);
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	static int s[MAXN];
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		char ch;is>>ch;
		s[i]=ch-'0';
	}
	int64 Ans=Manacher(s,n);
	os<<Ans<<'\n';
	return 0;
}