首页 > 代码库 > BZOJ 2084 [Poi2010]Antisymmetry（manacher）
BZOJ 2084 [Poi2010]Antisymmetry（manacher）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2084
【题目大意】
对于一个01字符串，如果将这个字符串0和1取反后，
再将整个串反过来和原串一样，就称作“反对称”字符串。
比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。
【题解】
修改manacher的判定条件，对该串进行计算即可。
【代码】
#include <cstdio>#include <cstring>using namespace std;const int N=1000010; int n,m,i,r,p,f[N<<1];long long ans;char a[N],s[N<<1];int min(int a,int b){return a<b?a:b;}bool check(char x,char y){ if(x==‘#‘&&y==‘#‘)return 1; if((x-‘0‘)+(y-‘0‘)==1)return 1; return 0;}void manacher(char *a){ for(i=1;i<=n;i++)s[i<<1]=a[i],s[i<<1|1]=‘#‘; s[0]=‘$‘,s[1]=‘#‘,s[m=(n+1)<<1]=‘&‘; for(r=p=0,f[1]=1,i=1;i<m;ans+=f[i++]>>1){ for(f[i]=r>i?min(r-i,f[p*2-i]):0;check(s[i-f[i]],s[i+f[i]]);f[i]++); if(i+f[i]>r)r=i+f[i],p=i; //printf("%d\n",f[i]); }}int main(){ scanf("%d",&n); scanf(" %s",a+1); manacher(a); printf("%lld\n",ans); return 0; }BZOJ 2084 [Poi2010]Antisymmetry（manacher）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。