CodeForces - 519D（思维+前缀和）

佚名 6年前 (2019-12-12) 算法 2011人围观抢沙发百度已收录

题意

https://vjudge.net/problem/CodeForces-519D

给定每个小写字母一个数值，给定一个只包含小写字母的字符串 s，求 s 的子串 t 个数，使 t满足：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

首位字母相同，长度大于 1。
首尾字母除外的其余字母的数值之和为 0。

思路

考虑abca的值为1 1 -1 1，前缀和为1 2 1 0，用map维护每个字符的各前缀和的个数，设两个a位置分别为l，r，那么对于后一个a它的答案是map[a][preR]，因为l+1~r-1的和为0，所以pre[L]=pre[R-1]。

代码

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N = 200005;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x & (-x))
ll a[N], pre = 0;
int main()
{
    std::ios::sync_with_stdio(false);
    for (int i = 0; i < 26; i++)
    {
        cin >> a[i];
    }
    string s;
    cin >> s;
    int l = s.length();
    map<ll, ll> mp[27];
    ll ans = 0;
    for (int i = 0; i < l; i++)
    {
        int c = s[i] - 'a';
        ans += mp[c][pre];
        pre += a[c];
        mp[c][pre]++;
    }
    cout << ans << endl;
    return 0;
}