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]を開けばいいです.
26文字のアルファベットはそれぞれ好みの度合いを与え、正負の整数で表す.次に、アルファベットのみを含む文字列Sが与えられ、TがSサブストリングである場合、Tの最初の文字は最後の文字と同じであり、最初の文字と最後の文字を除いて、文字の愛着度と0は、要求に合致するサブストリングである.全部でどれだけの要求に合致する子列があることを求めます.
ここで接頭辞とsum[i],S[i]=S[k](k>i)を維持すると,中間文字の愛着度と0はsum[i]=sum[k]-val[k]に変換される.ではmap
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 }