Sol
Manacher.
\(O(n)\) Manacher很简单啊.改一改转移就可以了.
然后我WA了.一开始天真的认为id只会是奇数,然后就GG.
一组 Hack 数据
3
1 0 0
然后就跳过偶数的拓展...就过了...
Code
/**************************************************************
Problem: 2084
User: BeiYu
Language: C++
Result: Accepted
Time:24 ms
Memory:9100 kb
****************************************************************/ #include<cstdio>
#include<iostream> using namespace std; const int N = 500050;
typedef long long LL; int n,m;LL ans;
int ch[N<<1],p[N<<1]; inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
inline char mychar(char ch=getchar()){ while(ch>'1'||ch<'0') ch=getchar();return ch; } int main(){
// freopen("in.in","r",stdin);
n=in(),m=2*n+1;ch[0]=888,ch[1]=19,ch[m+1]=666;
for(int i=1;i<=n;i++) ch[i<<1]=mychar()-'0',ch[i<<1|1]=19;
int mx=0,id=0;
for(int i=1;i<=m;i+=2){
if(mx>i) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(ch[i+p[i]]+ch[i-p[i]]==1||ch[i+p[i]]+ch[i-p[i]]==38) p[i]++;
if(i+p[i]>mx) mx=i+p[i],id=i;
} // for(int i=1;i<=m;i++) printf("%2d ",ch[i]);cout<<endl;
// for(int i=1;i<=m;i++) printf("%2d ",p[i]);cout<<endl;
for(int i=1;i<=m;i+=2) ans+=(p[i]-1)>>1;
printf("%lld\n",ans);
return 0;
}