ACdreamoj 1011(树状数组维护字符串hash前缀和)-白红宇

ACdreamoj 1011(树状数组维护字符串hash前缀和)

阅读量：7026 次

发布时间：2019-06-28

本文共 3808 字，大约阅读时间需要 12 分钟。

题目链接：http://acdream.info/problem?

pid=1019

题意：两种操作，第一种将字符串某个位置的字符换为还有一个字符。另外一种查询某个连续子序列是否是回文串；

解法：有两种hash的办法，所以写了两种解法;首先hash是x1 * p^1+ x2*p^2 +x3*p^3...能够用树状数组维护前缀和，维护两个串，一个是正串。还有一个是反串用于比較。比較时候乘以对应的p倍数推断是否相等。

刘汝佳白书上的hash方法处理这道题更复杂：改动i会对后缀j产生的影响为a*p^(i-j)，那么把这个式子变成a * p^i *p^(-j) 然后就是在这个位置加上a * p^i，以后查询每一个i位置的hash值后都乘以p^i.

第一分代码：

/******************************************************* @author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8#define zero(_) (abs(_)<=eps)const double pi=acos(-1.0);typedef unsigned long long LL;const int Max=1000010;const int INF=1e9+7;char s[Max];LL C[2][Max];LL Hash[Max];int seed=13;void init(){ Hash[0]=1; for(int i=1; i
                 
                  >t; len=strlen(s+1); for(int i=1; i<=len; i++) { update(0,i,(s[i]-'a')*Hash[i]); update(1,len+1-i,(s[i]-'a')*Hash[len+1-i]); } while(t--) { char c; getchar(); scanf("%c",&c); if(c=='C') { char b[5]; int a; scanf("%d%s",&a,b); update(0,a,-(s[a]-'a')*Hash[a]); update(0,a,(b[0]-'a')*Hash[a]); update(1,len+1-a,-(s[a]-'a')*Hash[len+1-a]); update(1,len+1-a,(b[0]-'a')*Hash[len+1-a]); s[a]=b[0]; } else { int l,r; scanf("%d%d",&l,&r); if(gethash(0,l,r)*Hash[len-l]==gethash(1,len+1-r,len+1-l)*Hash[r-1]) puts("yes"); else puts("no"); } } } return 0;}

第二份代码：

/******************************************************* @author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8#define zero(_) (abs(_)<=eps)const double pi=acos(-1.0);typedef unsigned long long LL;const int Max=1000010;const LL INF=1000000007;char s[Max];char s2[Max];LL Hash[Max];LL C[Max];LL C2[Max];int seed=13;int len;void init(){ Hash[0]=1; for(int i=1; i
                 
                  >=1; } return ans;}void update(int pos,LL value){ while(pos!=0) { C[pos]=(C[pos]+value+INF)%INF; pos-=pos&(-pos); }}void update2(int pos,LL value){ while(pos!=0) { C2[pos]=(C2[pos]+value+INF)%INF; pos-=pos&(-pos); }}LL query(int pos){ LL ans=0; while(pos<=len+1) { ans=(ans+C[pos])%INF; pos+=pos&(-pos); } return ans;}LL query2(int pos){ LL ans=0; while(pos<=len+1) { ans=(ans+C2[pos])%INF; pos+=pos&(-pos); } return ans;}LL get(int now){ LL ans=query(now); return (pow1(pow1(seed,now),INF-2)%INF*ans)%INF;}LL gethash(int l,int r){ return (get(l)-get(r+1)*Hash[r+1-l]%INF+INF)%INF;}LL get2(int now){ LL ans=query2(now); return (pow1(pow1(seed,now),INF-2)%INF*ans)%INF;}LL gethash2(int l,int r){ return (get2(l)-get2(r+1)*Hash[r+1-l]%INF+INF)%INF;}int main(){ init(); while(scanf("%s",s+1)==1) { int t; scanf("%d",&t); len=strlen(s+1); strcpy(s2+1,s+1); reverse(s2+1,s2+len+1); memset(C,0,sizeof C); memset(C2,0,sizeof C2); for(int i=1; i<=len; i++) { update(i,(s[i]-'a')*Hash[i]%INF);//a*x^(i-j)=a*x^i*(x^-j); update2(i,(s2[i]-'a')*Hash[len+1-i]%INF); } while(t--) { char c[5]; scanf("%s",c); //printf(c); if(c[0]=='C') { int a; char b[5]; scanf("%d%s",&a,b); update(a,('a'-s[a])*Hash[a]%INF); update(a,(b[0]-'a')*Hash[a]%INF); update2(len+1-a,('a'-s2[len+1-a])*Hash[len+1-a]%INF); update2(len+1-a,(b[0]-'a')*Hash[len+1-a]%INF); s[a]=b[0]; s2[len+1-a]=b[0]; } else { int l; int r; scanf("%d%d",&l,&r); if(r-l<=1) { puts("yes"); continue; } if(gethash(l,r)==gethash2(len+1-r,len+1-l)) puts("yes"); else puts("no"); } } } return 0;}

转载地址：http://uxoxl.baihongyu.com/

你可能感兴趣的文章