The Preliminary Contest for ICPC Asia Xuzhou 2019 G. Colorful String 回文树-白红宇

The Preliminary Contest for ICPC Asia Xuzhou 2019 G. Colorful String 回文树

阅读量：5029 次

发布时间：2019-06-12

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

签到提；

题意：求出每一个回文串的贡献 (贡献的计算就是回文串不同字符的个数)

题解：

用回文树直接暴力即可

回文树开一个数组cost[ ][26] 和val[ ] 数组；

val【i】表示回文树上节点 i 的对应的回文的贡献

最后统计答案即可

LL get_ans() {
      LL ans = 0;     for (int i = sz - 1; i >= 0; --i) ans += 1LL * cnt[i] * val[i];     return ans; }

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     = 0; --i)cnt[fail[i]] += cnt[i];101 //逆序累加，保证每个点都会比它的父亲节点先算完，于是父亲节点能加到所有子孙102 }103 104 LL get_ans() {105 LL ans = 0;106 for (int i = sz - 1; i >= 0; --i) ans += 1LL * cnt[i] * val[i];107 return ans;108 }109 } pam;110 111 int main() {112 FIN;113 sfs(s + 1);114 pam.init();115 int n = strlen(s + 1);116 for (int i = 1; i <= n; i++) {117 pam.add(s[i], i);118 }119 pam.count();120 LL ans = pam.get_ans();121 printf("%lld\n", ans);122 return 0;123 }