Codeforces Round #294 (Div. 2) D. A and B and Interesting Substrings

5000 ワード

タイトルアドレス:http://codeforces.com/contest/519/problem/D
    26文字のアルファベットはそれぞれ好みの度合いを与え、正負の整数で表す.次に、アルファベットのみを含む文字列Sが与えられ、TがSサブストリングである場合、Tの最初の文字は最後の文字と同じであり、最初の文字と最後の文字を除いて、文字の愛着度と0は、要求に合致するサブストリングである.全部でどれだけの要求に合致する子列があることを求めます.
    ここで接頭辞とsum[i],S[i]=S[k](k>i)を維持すると,中間文字の愛着度と0はsum[i]=sum[k]-val[k]に変換される.ではmapm[26]を開けばいいです.
 1 #include<cstdio>

 2 #include<iostream>

 3 #include<string.h>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<stdbool.h>

 7 #include<map>

 8 #include<stack>

 9 using namespace std;

10 #define clr(x,y)    memset(x,y,sizeof(x))

11 #define sqr(x)      ((x)*(x))

12 #define rep(i,a,b)  for(int i=(a);i<=(b);i++)

13 #define LL          long long

14 #define INF         0x3f3f3f3f

15 #define A           first

16 #define B           second

17 

18 int main()

19 {

20     int val[30];

21     char a[100005];

22     LL rez=0,sum=0;

23     

24     map<LL,int> m[30];

25     for(int i=0;i<26;i++) {

26         scanf("%d",&val[i]);

27     }

28     getchar();

29     gets(a);

30     

31     int len=strlen(a);

32     for(int i=0;i<len;i++) {

33         a[i]-='a';

34         sum+=val[a[i]];

35         rez+=m[a[i]][sum-val[a[i]]];

36         m[a[i]][sum]++;    

37     }

38     

39     cout<<rez<<endl;

40     

41 }