Note
In the first sample test strings satisfying the condition above areabcaandbcab.
In the second sample test strings satisfying the condition above are two occurences ofaa.
题意：第一行给出每个字母的价值val，第二行是一个字符串，在字符串中找到满足如下条件的子串的个数：
1.首尾字母相同
2.除首尾外其他字母价值总和为0
有两个条件而且数据量是10^5 ，，所以要找一个接近线性复杂度的方法
所以可以想到以前i项价值和建数组，每个价值和对应的26个字母分别有多少个即可
这样会超内存的所以我用了离散化，就ac了…也正因为2在这里…直接用map处理就相当于离散化了….
我的代码：
//Memory: 12600 KBTime: 31 MS#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;#define M 100010#define ll long longint val[30];struct node {int tab;ll a;}sum[M];char s[M];ll tmp;int Hash[M];int cnt[M][27];ll ans;bool cmp(const node&a,const node&b){return a.a<b.a;}int main(){for(int i=0;i<26;i++){scanf("%d",&val[i]);}scanf("%s",s);int len =strlen(s);for(int i=0;i<len;i++){tmp+=val[s[i]-'a' ];sum[i].tab=i;sum[i].a=tmp;}sort(sum,sum+len,cmp);int l=0;Hash[sum[0].tab ]=l;for(int i=1;i<len;i++){//离散化…if(sum[i].a==sum[i-1].a){Hash[sum[i].tab ]=l;}else Hash[sum[i].tab ]=++l;}cnt[Hash[0]][s[0]-'a']++;for(int i=1;i<len;i++){ans+=cnt[Hash[i-1] ][s[i]-'a' ];cnt[Hash[i] ][s[i]-'a']++;}printf("%I64d\n",ans);return 0;}大神的代码：
// 75ms#include<iostream>#include<fstream>#include<cstdio>#include<vector>#include<string>#include<cstring>#include<queue>#include<map>#include<set>#include<algorithm>#include<iomanip>#include<bitset>using namespace std;const int N = 100100;int val[27];char a[N];int n;map<long long, int> h[26];int main() {int i;for(i = 0; i < 26; ++i) {cin >> val[i];}cin >> (a + 1);n = strlen(a + 1);long long sc = 0, rez = 0;for(i = 1; i <= n; ++i) {a[i] -= 'a';sc += val[a[i]];rez += h[a[i]][sc – val[a[i]]];h[a[i]][sc]++;}cout << rez;return 0;}
风不懂云的漂泊，天不懂雨的落魄，眼不懂泪的懦弱，
