[POI2010]Antisymmetry

Description

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

Input

第一行一个正整数N (N <= 500,000)。第二行一个长度为N的01字符串。

Output

一个正整数，表示反对称子串的个数。

Sample Input

8

11001011

Sample Output

7

//7个反对称子串分别是：01(出现两次), 10(出现两次), 0101, 1100和001011

Manacher，不多说……不过，怎么匹配呢？肯定不是直接匹配。我们将原串转换一下，把1改为2，0不变，中间添加1，那么我们匹配的时候就看看两个点是否相加等于2即可

统计答案？由于反对称子串一定是偶串，所以我们只要枚举1所在的位置。

那么答案是什么？p[i]/2。为什么？因为我们匹配的时候，是看两个点是否相加为2，那么匹配的两个点要么是1，要么是0和2。这样，回文半径每增加2，答案的个数就增加了1，所以直接累加 p[i]/2 即可。

初始值为1？整除把它干掉了……

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)     print(x/10);

	putchar(x%10+'0');

}

const int N=5e5;

char s[N+10];

int val[N*2+10],p[N*2+10];

ll Ans;

int main(){

	int len=read();

	scanf("%s",s+1);

	for (int i=1;i<=len;i++)	val[i<<1]=s[i]-'0'?2:0,val[i<<1|1]=1;

	len=len<<1|1;

	val[1]=1,val[0]=val[len+1]=-1;

	int Max=0,ID=0;

	for (int i=1;i<=len;i++){

		p[i]=Max>i?min(p[ID*2-i],Max-i):1;

		while (val[i+p[i]]+val[i-p[i]]==2)	p[i]++;

		if (Max<p[i]+i-1)	Max=p[ID=i]+i-1;

	}

	for (int i=1;i<=len;i+=2)	Ans+=p[i]>>1;

	printf("%lld\n",Ans);

	return 0;

}

巴特西

[POI2010]Antisymmetry

最新文章

热门文章