題意
https://vjudge.net/problem/CodeForces-519D
給定每個小寫字母一個數值，給定一個只包含小寫字母的字串 s，求 s 的子串 t 個數，使 t滿足：
- 首位字母相同，長度大于 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117910.html
標籤：其他