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

题目链接：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;

}

　　

[CF Round #294 div2] D. A and B and Interesting Substrings 【Map】的相关教程结束。