求一個(gè)01序列的子串取反并反轉(zhuǎn)后與原串相同的個(gè)數(shù).

很顯而易見的是，反轉(zhuǎn)的話只要子串對(duì)應(yīng)的i和n-i+1位相反即可,這個(gè)看一下樣例能很快看出來(lái).

所以我們正著求一遍hash,反著取反然后求hash.

枚舉中間點(diǎn),二分一下這個(gè)子串長(zhǎng)度的一半,check的話就是判斷前一半子串的正hash值與后一半子串取反后的反hash值是否相等.

答案怎么統(tǒng)計(jì)呢,顯然,如果一個(gè)子串滿足條件,那么去掉首位得到的子串也滿足條件,ans+=len/2...

然而細(xì)節(jié)寫錯(cuò)wa了2發(fā)。。。

1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%lld ",a) 10 #define writeln printf("\n") 11 const int N=5e5+50; 12 const int MOD=1e9+7; 13 const int base=233; 14 using namespace std; 15 int n; 16 char s[N]; 17 ll Hash1[N],Hash2[N],Pow[N]; 18 ll ans; 19 int read() 20 { 21 int s=0,t=1; char c; 22 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 23 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 24 return s*t; 25 } 26 ll readl() 27 { 28 ll s=0,t=1; char c; 29 while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();} 30 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 31 return s*t; 32 } 33 ll get(int l,int r,int x) 34 { 35 if (x==1) return (Hash1[r]-(ll)Hash1[l-1]*Pow[r-l+1]%MOD+MOD)%MOD; 36 return (Hash2[l]-(ll)Hash2[r+1]*Pow[r-l+1]%MOD+MOD)%MOD; 37 } 38 int solve(int x) 39 { 40 int l=1,r=min(x,n-x),mid=0; bool flag=false; 41 while (l<=r){ 42 mid=(l+r)>>1; 43 if (get(x-mid,x+mid-1,1)==get(x-mid,x+mid-1,2)) flag=true,l=mid+1; 44 else r=mid-1; 45 } 46 //out(x),out(r),writeln; 47 if (flag) return r; 48 return 0; 49 } 50 int main() 51 { 52 n=read(); Pow[0]=1; 53 scanf("%s",s); 54 for (int i=1;i<=n;i++) 55 Pow[i]=Pow[i-1]*base%MOD; 56 for (int i=0;i<n;i++) 57 Hash1[i]=(Hash1[i-1]*base+s[i])%MOD; 58 for (int i=n-1;i>=0;i--) 59 Hash2[i]=(Hash2[i+1]*base+(48+49-s[i]))%MOD; 60 for (int i=1;i<n;i++) 61 ans+=solve(i); 62 out(ans); 63 return 0; 64 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Kaleidoscope233/p/9563082.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2084: [Poi2010]Antisymmetry(Hash+二分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。