题目链接：D. A and B and Interesting Substrings
题目大意
给定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 <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map> 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<LL, int> 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;
}