[CF Round #294 div2] D. A and B and Interesting Substrings 【Map】-白红宇

[CF Round #294 div2] D. A and B and Interesting Substrings 【Map】

阅读量：4607 次

发布时间：2019-06-09

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

题目链接：

题目大意

给定26个小写字母的权值，一共26个整数（有正有负）。

给定一个小写字母组成的字符串（长度10^5），求有多少长度大于1的子串满足：

1）首尾字符相同。

2）除了首尾字符外，其他字符的权值和为0。

题目分析

使用STL Map。开26个Map，给每个字母开一个。

先求出权值的前缀和 Sum[] 。

然后1到l枚举每一位字符，如果是a，那么 Ans += Map[a][Sum[i - 1]];

然后 ++Map[a][Sum[i]];

这个原理是十分简单的，但是我就是这么弱，以至于比赛的时候想不到，然后用了一种复杂的方法，最后WA了= =

时间复杂度 O(n log n) 。

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;}typedef long long LL;typedef unsigned long long ULL;const int MaxL = 100000 + 5, MaxC = 26 + 5;int l;int V[MaxC], A[MaxL];LL Ans;LL Sum[MaxL];char S[MaxL];map
            
              Mp[MaxC];int main() { for (int i = 0; i < 26; ++i) scanf("%d", &V[i]); scanf("%s", S + 1); l = strlen(S + 1); for (int i = 1; i <= l; ++i) A[i] = S[i] - 'a'; Sum[0] = 0ll; Ans = 0ll; for (int i = 1; i <= l; ++i) Sum[i] = Sum[i - 1] + (LL)V[A[i]]; for (int i = 0; i < 26; ++i) Mp[i].clear(); for (int i = 1; i <= l; ++i) { Ans += (LL)Mp[A[i]][Sum[i - 1]]; ++Mp[A[i]][Sum[i]]; } cout << Ans << endl; return 0;}