bzoj-2084 Antisymmetry

 题意：

定义一个串反对称 为 将其01取反之后，翻转之后与原串相同；

给出一个长度为n的01串，求这个串中有多少子串为反对称串；

n<=500000；

题解：

马拉车算法。。

然而作为一个蒟蒻我还是滚回去复习了一遍manacher啥的；

首先这题有个性质：反对称串一定是偶数长的串；

所以我们其实跑的只是偶数串的算法，也就是可以不加#分隔的姿势；

(你不觉得不加#####十分优雅吗？)

然后改一下判断参数就是反对称串了；

对于算法的实现细节就看代码吧，这题也真是没啥说的；

时间复杂度O(n)；

代码：

#include<cctype>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 531072
using namespace std;
bool str[N];
int f[N];
int main()
{
    int n,m,i,j,k,id,ma;
    long long ans;
    char ch;
    scanf("%d",&n);
    while(!isdigit(ch=getchar()));
    str[1]=ch-'0';
    for(i=2;i<=n;i++)
        str[i]=getchar()-'0';
    for(i=1,ma=0,id=0,ans=0;i<=n;i++)
    {
        if(f[i]<=ma)
            f[i]=max(f[i],min(f[id+id-i],ma-i));
        while(str[i+f[i]+1]==!str[i-f[i]]&&i+f[i]+1<=n&&i-f[i]>0)
            f[i]++;
        if(i+f[i]>ma)
            ma=i+f[i],id=i;
        ans+=f[i];
    }
    printf("%lld\n",ans);
    return 0;
}

bzoj-2084 Antisymmetry

原文：http://blog.csdn.net/ww140142/article/details/48648861