ZROI2018提高day3t3-白红宇

ZROI2018提高day3t3

阅读量：7096 次

发布时间：2019-06-28

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

分析

我们对于每一个可以匹配的字符都将其从栈中弹出，然后他的哈希值就是现在栈中的字符哈希一下。然后我们便可以求出对于哪些位置它们的哈希值是一样的，即它们的状态是一致的。而这些点可以求出它们的贡献（这个式子见代码）。而这个式子的意义是对于左括号自然表示哪几个括号组成一个合法序列，而对于右括号则代表以几种不同的排列方式和之前的左括号进行匹配。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long mod = 1e9+9;long long n,cnt,a[1000100],i,j,ans;unsigned long long p[1000100],q[1000100];char s[1000100];int main(){ scanf("%s",s); n=strlen(s); q[0]=1; p[0]=0; for(i=1;i<=n;i++)q[i]=q[i-1]*1313; for(i=0;i
                   
                    1&&a[cnt]==a[cnt-1])p[i]=p[i-1]-a[cnt-1]*q[cnt-1],cnt-=2; else p[i]=p[i-1]+a[cnt]*q[cnt]; } sort(p,p+n+1); for(i=0,j=0;i<=n;i=j){ while(j<=n&&p[i]==p[j])j++; ans+=(j-i)*(j-i-1)/2; } cout<
                    
                     <

转载于:https://www.cnblogs.com/yzxverygood/p/9649996.html

你可能感兴趣的文章