UPC OJ 一道水题 STL

Problem C: 字符串游戏

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 10  Solved: 3 [Submit][Status][Web Board]

Description

说到游戏，大家还是比较喜欢的，但是玩游戏，如果想赢得对方还是得靠思维的，xy比较喜欢字符串，尤其是起始字母等于终止字母这样的字符串(the string's length must exceed one)，但是呢，xy有个癖好，喜欢把每个字符重新分配一个值，喜欢的字符给非负数，不喜欢的字符给负数。但是，xy比较喜欢数字0，所以，他决定找到一个字符串中有多少个字串满足起始字母等于终止字母，且除了起始字母和终止字母外其他字母的和为0。但是xy最近比较忙，希望你能帮助他。

Input

第一行包含26个整数xi，xi属于[-100000,100000]，非别代表着小写字母a,b,c,....,z的值。

第二行一个只包含小写字母的字符串，长度你自己猜，算了，给你个范围，length between 1 and 100000.

Output

输出答案，每个答案占一行。

Sample Input

1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1

xabcab

Sample Output

2

题目分析：

每种字母的字符串求一遍，预处理前缀和，每次查找到一个位置i，查询前面有多少与sum[i-1]相同的以该子母为结尾的sum[j]，用mp实现，总复杂度O(nlogn)
刚开始用了multiset中的count函数，总是超时，最后据我推断，那是因为count函数的时间复杂度是O(klogn)，k是相同的个数，唉，还是太年轻。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<iostream>

#include<cstdlib>

#include<queue>

#include<map>

using namespace std;

typedef long long LL;

char s[];

LL a[],sum[];

map<LL,int>mp;

vector<int>b[];

int main()

{

    for(int i=; i<; ++i)

        scanf("%lld",&a[i]);

    scanf("%s",s+);

    int len=strlen(s+);

    sum[]=;

    long long ans=;

    for(int i=; i<=len; ++i)

    {

        int c=s[i]-'a';

        sum[i]=sum[i-]+a[c];

        b[c].push_back(i);

    }

    for(int i=; i<; ++i)

    {

        mp.clear();

        for(int j=; j<b[i].size(); ++j)

        {

            if(j>)ans+=mp[sum[b[i][j]-]];

            mp[sum[b[i][j]]]++;

        }

    }

    printf("%lld\n",ans);

    return ;

}

/**************************************************************

    Problem: 3285

    User: 1407010221

    Language: C++

    Result: Accepted

    Time:204 ms

    Memory:2956 kb

****************************************************************/