[CF 519D] A and B and Interesting Substrings

作法：

題目等價於要找滿足「 i>=j , sum[ i ] = sum[ j ] , a[ i+1 ] = a[ j ] 」 的 ( i , j ) 組數，sum 是字母得分從 1 加到 i 的值，a 是原本的字串。所以直接用 pair 把 ( sum[ i ] , a[ i ] ) 包起來，用 map 記錄每個 pair 出現了幾次，然後作到 i 的時候直接查詢就好了。

然後記得 sum 要開 long long ，我有 hack 到一個沒開 long long 的人 XD

code :

#include<bits/stdc++.h>
#define LL long long
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=100000+10 ;
 
map< pair<LL,char>,int > mp ;
int w[27] ;
char s[maxn] ;
LL sum[maxn] ;
main()
{
    for(int i=0;i<26;i++) scanf("%d",&w[i]) ;
    scanf("%s",s+1) ;
    int n=strlen(s+1) ;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[s[i]-'a'] ;
    LL ans=0LL ;
    for(int i=1;i<n;i++)
    {
        mp[mkp(sum[i],s[i])]++ ;
        ans+=mp[mkp(sum[i],s[i+1])] ;
    }
    printf("%I64d\n",ans) ;
}