bzoj2084【POI2010】Antisymmetry

Description

對於一個01字符串，如果將這個字符串0和1取反後，再將整個串反過來和原串一樣，就稱作“反對稱”字符串。比如00001111和010101就是反對稱的，1001就不是。
現在給出一個長度為N的01字符串，求它有多少個子串是反對稱的。

Input

第一行一個正整數N (N <= 500,000)。第二行一個長度為N的01字符串。

Output

一個正整數，表示反對稱子串的個數。

Sample Input

Sample Output

Source

方法一：二分+哈希

枚舉中間點，然後二分長度，用哈希判斷是否滿足反對稱。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define base 233
using namespace std;
int n,a[maxn],b[maxn];
ll ans;
ull fa[maxn],fb[maxn],p[maxn];
char s[maxn];
inline ull hasha(int l,int r)
{
	return fa[r]-fa[l-1]*p[r-l+1];
}
inline ull hashb(int l,int r)
{
	return fb[l]-fb[r+1]*p[r-l+1];
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	F(i,1,n) a[i]=s[i]-'0',b[i]=a[i]^1;
	F(i,1,n) fa[i]=fa[i-1]*base+a[i];
	D(i,n,1) fb[i]=fb[i+1]*base+b[i];
	p[0]=1;F(i,1,n) p[i]=p[i-1]*base;
	F(i,1,n-1)
	{
		int l=1,r=min(i,n-i),mid,tmp=0;
		while (l<=r)
		{
			mid=(l+r)>>1;
			if (hasha(i-mid+1,i+mid)==hashb(i-mid+1,i+mid)) tmp=mid,l=mid+1;
			else r=mid-1;
		}
		ans+=tmp;
	}
	printf("%lld\n",ans);
	return 0;
}

方法二：manacher

令0=1，0≠0，1≠1，#=#，然後跑manacher。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define ull unsigned long long
#define maxn 1000005
using namespace std;
int n,f[maxn];
ll ans;
char ch[maxn],s[maxn];
inline bool judge(char a,char b)
{
	return (a=='#'&&b=='#')||(a=='0'&&b=='1')||(a=='1'&&b=='0');
}
inline void manacher()
{
	int mx=0,id=0;
	F(i,1,n)
	{
		if (mx>i) f[i]=min(f[id*2-i],mx-i);
		else f[i]=0;
		while (judge(s[i-f[i]],s[i+f[i]])) f[i]++;
		if (i+f[i]>mx) mx=i+f[i],id=i;
		ans+=(f[i]>>1);
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%s",ch+1);
	s[1]='#';
	F(i,1,n) s[i<<1]=ch[i],s[i<<1|1]='#';
	n=n<<1|1;
	manacher();
	printf("%lld\n",ans);
	return 0;
}