首页 > 代码库 > Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E DNA Evolution

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E DNA Evolution

DNA Evolution

题目让我们联想到树状数组或者线段树,但是如果像普通那样子统计一段的和,空间会爆炸。

所以我们想怎样可以表示一段区间的字符串。

学习一发大佬的解法。

开一个C[10][10][4][n],就可以啦,第二维表示e的长度,第一维表示i%e的长度,第三维表示颜色,第四维求和了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+5;
 4 char s[maxn];
 5 map<char,int> mp;
 6 int C[12][12][4][maxn];
 7 int n = 0;
 8 void add(int a,int b,int c,int d,int x)
 9 {
10     while(d<=n)
11     {
12         C[a][b][c][d] += x;
13         d += (d&-d);
14     }
15 }
16 int sum(int a,int b,int c,int d)
17 {
18     int res = 0;
19     while(d>0)
20     {
21         res += C[a][b][c][d];
22         d -= (d&-d);
23     }
24     return res;
25 }
26 int main()
27 {
28     mp[A] = 0;
29     mp[T] = 1;
30     mp[G] = 2;
31     mp[C] = 3;
32     cin>>(s+1);
33     n = strlen(s+1);
34     //cout<<(s+1)<<endl;
35     int q,l,r;
36     char e[11];
37     for(int i=1;i<=n;i++)
38     {
39         for(int j=1;j<=10;j++)
40         {
41             add((i-1)%j,j,mp[s[i]],i,1);
42         }
43     }
44     cin>>q;
45     while(q--)
46     {
47         int mark = 0;
48         cin>>mark;
49         if(mark==1)
50         {
51             cin>>r>>e;
52             for(int j=1;j<=10;j++)
53             {
54                 add((r-1)%j,j,mp[s[r]],r,-1);
55                 add((r-1)%j,j,mp[e[0]],r,1);
56             }
57             s[r] = e[0];
58         }
59         else
60         {
61             cin>>l>>r>>e;
62             int res = 0;
63             int elen = strlen(e);
64             for(int i=0;i<elen;i++)
65             {
66                // cout<<sum((l+i-1)%elen,elen,mp[e[i]],r)<<endl;
67                 res += (sum((l+i-1)%elen,elen,mp[e[i]],r)-sum((l+i-1)%elen,elen,mp[e[i]],l-1));
68             }
69             cout<<res<<endl;
70         }
71     }
72     return 0;
73 }
74 /*
75 A
76 11
77 2 1 1 GCA
78 1 1 T
79 2 1 1 AACGACTG
80 2 1 1 GA
81 2 1 1 C
82 1 1 A
83 1 1 G
84 1 1 A
85 1 1 G
86 1 1 G
87 2 1 1 AG
88 */

 

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E DNA Evolution