BZOJ2084：[POI2010]Antisymmetry

浅谈\(Manacher\)：https://www.cnblogs.com/AKMer/p/10431603.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2084

题目求的就是偶数长度回文串个数。不过匹配从相等变成了异或等于\(1\)，在\(Manacher\)算法上稍作改进即可。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int n,ans;

int p[maxn];

char s[maxn];

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*10+ch-'0';

	return x*f;

}

int main() {

	n=read(),scanf("%s",s+1);

	for(int i=n;i;i--)

		s[i<<1]=s[i],s[(i<<1)-1]='#';

	s[0]='$',s[n<<1|1]='#',n=n<<1|1;

	int id=0,mx=0;

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

		p[i]=i<=mx?min(mx-i+1,p[(id<<1)-i]):1;

		while(s[i-p[i]]-'0'+s[i+p[i]]-'0'==1||s[i-p[i]]=='#')p[i]++;

		if(s[i]=='#')ans+=(p[i]-1)/2;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ2084：[POI2010]Antisymmetry

最新文章

热门文章