cjb-poi2010antisymmetry

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 510000
char s[N];
int s1[N<<1];
int p[N<<1];
int n;
int main()
{
    cin>>n;
    scanf("%s",s);
    s1[0]=999,s1[1]=1;
    for(int i=1;i<=n;i++)s1[i<<1]=s[i-1]=='1'?2:0,s1[i<<1|1]=1;
    n<<=1,n++;
    int id,mx=0;
    for(int i=1;i<n;i+=2)
    {
        if(mx>i)p[i]=min(p[id*2-i],mx-i);
        else p[i]=1;
        while(s1[i-p[i]]+s1[i+p[i]]==2&&i-p[i]>0&&i+p[i]<n)p[i]++;
        if(i+p[i]>mx)mx=i+p[i],id=i;
    }
    long long ans=0;
    for(int i=1;i<n;i+=2)ans+=(p[i]>>1);
    cout<<ans<<endl;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 510000
char s[N];
int s1[N<<1];
int p[N<<1];
int n;
int main()
{
    cin>>n;
    scanf("%s",s);
    s1[0]=999,s1[1]=1;
    for(int i=1;i<=n;i++)s1[i<<1]=s[i-1]=='1'?2:0,s1[i<<1|1]=1;
    n<<=1,n++;
    int id,mx=0;
    for(int i=1;i<n;i+=2)
    {
        if(mx>i)p[i]=min(p[id*2-i],mx-i);
        else p[i]=1;
        while(s1[i-p[i]]+s1[i+p[i]]==2&&i-p[i]>0&&i+p[i]<n)p[i]++;
        if(i+p[i]>mx)mx=i+p[i],id=i;
    }
    long long ans=0;
    for(int i=1;i<n;i+=2)ans+=(p[i]>>1);
    cout<<ans<<endl;
}