若一个01串，先将01取反后，再将整个串翻转，如果能得到原来的01串，则说明这个串反对称
给出一个长度为n个01串，求出有多少个子串是反对称的
Manacher好题
将回文的意义变为相对位置互不相同就行了
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; char cc[1100000],st[1100000]; int p[1100000]; int n; void Manacher() { st[1]=‘#‘; for(int i=1;i<=n;i++) st[2*i]=cc[i],st[2*i+1]=‘#‘; int len=2*n+1; int pos=0,R=0; for(int i=1;i<=len;i++) { int j=2*pos-i; if(i<=R) p[i]=min(p[j],R-i); else p[i]=0; while(1<=i-p[i]&&i+p[i]<=len&&(st[i-p[i]]!=st[i+p[i]]||st[i-p[i]]==‘#‘)) p[i]++; if(i+p[i]-1>R){R=i+p[i]-1;pos=i;} } } int main() { scanf("%d",&n); scanf("%s",cc+1); Manacher(); int ans=0; for(int i=3;i<=n*2+1;i+=2) { ans+=(p[i]-1)/2; } printf("%d\n",ans); return 0; }
BZOJ2084: [Poi2010]Antisymmetry
原文：https://www.cnblogs.com/Never-mind/p/9728850.html