【BZOJ】2084: [Poi2010]Antisymmetry

http://www.lydsy.com/JudgeOnline/problem.php?id=2084

题意：一个01串，求满足字符串0和1取反后，再将整个串反过来和原串一样的子串数目。（n<=500000）

#include <bits/stdc++.h>

using namespace std;

const int N=500005;

long long ans;

int len[N<<1], n;

char s[N<<1];

int main() {

	scanf("%d%s", &n, s+1);

	for(int i=n; i; --i) s[i<<1]=s[i], s[i<<1|1]='#';

	n=n<<1|1; s[1]='#';

	int cur=1;

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

		int &now=len[i];

		now=min(len[(cur<<1)-i], max(0, cur+len[cur]-i));

		if(i&1) {

			while(i-now-1>=1 && i+now+1<=n && (s[i-now-1]=='#' || s[i-now-1]!=s[i+now+1])) ++now;

			ans+=now;

		}

		if(cur+len[cur]<i+now) cur=i;

	}

	printf("%lld\n", ans>>1ll);

	return 0;

}

发现就是0和1看做相等的回文串= =

妈呀发现在做manacher的时候有各种坑爹情况= =

首先要注意只能插入的特殊字符才能拓展= =否则如果是0或1拓展的话会出现莫名的问题= =（因为当0!=1的时候可能会造成类似这种

4
1001

答案应该是2

= =因为你会发现当'#'拓展后得到的长度，对于'0'或'1'在这个长度内不一定满足回文性= =

巴特西

【BZOJ】2084: [Poi2010]Antisymmetry

最新文章

热门文章