D. A and B and Interesting Substrings(前缀和+思维)

题目大意：
先输入26个字符[‘a’,‘z’]的权值，然后给你一个字符串，问你满足以下条件的子串有多少个。
1：第一个和最后一个字符相等的子串。
2：在这个子串中除掉第一个和最后一个字符的权值，剩下的字符权值之和等于0。
思路：求一段区间和我们可以用前缀和O(1)解决，但是要在一个串中找所有首位字符相等的子串的时间复杂度是O(n^2),因为N=1e5，这个时间复杂度肯定超时，所有我们要从别的角度解决这个问题。
前缀和等于0意味着：sum[r - 1] - sum[ l ] = 0（减掉第一个和最后一个字符的权值），只要稍微移一下项，就可以降维了。即sum[r - 1] = sum[ l ]。也就是说如果前缀和数组中，如果他们的前缀和的值相等，并且首尾字符相等，意味着他们满足条件。我们可以用一个map维护这个前缀和。mp [ i ] [ j ] [ k ] 表示字符’i’的前缀和为j的数量是k。
这样O(n)扫一遍字符就可以解决问题了，不过由于要删掉首尾字符的权值，即考虑当前字符的权值应该是不包括自己的权值。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
typedef long long int ll;
ll a[50],pre_s[maxn];
char s[maxn];
int main(){
	for(int i = 1; i <= 26; i++){
		cin>>a[i];
	}
	scanf("%s",s+1);
	int len = strlen(s + 1);
	for(int i = 1 ; i <= len; i++){
		pre_s[i] = pre_s[i-1] + a[s[i]-'a'+1];  
	}
	map<int,map<ll,ll> >mp;
	ll sum = 0,ans = 0;
	for(int i = 1; i <= len; i++){
		ans += mp[s[i] - 'a' + 1][sum];//先求答案后加当前的和
		sum += a[s[i] - 'a' +1];//前缀和
		mp[s[i] - 'a' + 1][sum]++;//计数
	}
	cout<<ans<<endl;
}

心得：map是个好东西，要活用。