A-D，补E，晚上做了两道睡觉了.......第二天早上起来做了C和D，合起来的时间估计是超了2小时了

A：模拟，if判断。

B：记录 ’B' 的数量和位置的最外层的上、下、左、右的坐标，取（下-上）和（右-左）的最大值L，若L小于n和m，成立L是边长，否则不成立，-1，保险起见，特判了B的数量是0和1的情况

C：暴力模拟，最后空位填‘a'，需要优化，对于每一次都是升序的位置，记录上一次的末尾，下一次就从这儿开始填

D：取定1为中心，向外扩展k个分支，一层层向外扩展，每个分支都只有一个子节点，

补E：树状数组，，，https://blog.csdn.net/KIDGIN7439/article/details/77769247

对给定查询e，计算e的位置i贡献的匹配数量即计算 (L + i), (L + i + len)， (L + i + 2 * len)。。。这些位置的匹配的数量，因此，我们对每个字母建立10 * 10个树状数组，[x][len]表示匹配位置 mod len = x的树状数组。对于更新位置为pos，就要对所有的len做一遍更新。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5  
 6 const int maxn = 1e5 + 10;
 7 int id[300], seg[13][13][6][maxn];
 8 char a[maxn], b[15];
 9  
10 int lowbit(int x)
11 {
12     return x & (-x);
13 }
14  
15 void add(int x, int y, int z, int pos, int v)
16 {
17     while (pos < maxn)
18     {
19         seg[x][y][z][pos] += v;
20         pos += lowbit(pos);
21     }
22 }
23  
24 int query(int x, int y, int z, int pos)
25 {
26     int ans = 0;
27     while (pos > 0)
28     {
29         ans += seg[x][y][z][pos];
30         pos -= lowbit(pos);
31     }
32     return ans;
33 }
34  
35 int main()
36 {
37     id['A'] = 0;
38     id['T'] = 1;
39     id['C'] = 2;
40     id['G'] = 3;
41     scanf("%s", a);
42     memset(seg, 0, sizeof(seg));
43     int q;
44     int lena = strlen(a);
45     for (int i = 1; i <= lena; i++)
46         for (int j = 1; j <= 10; j++)
47             add(i % j, j, id[a[i - 1]], i, 1);
48     scanf("%d", &q);
49     while (q--)
50     {
51         int x, y, z;
52         char ch;
53         scanf("%d", &x);
54         if (x == 1)
55         {
56             scanf("%d %c", &y, &ch);
57             for (int i = 1; i <= 10; i++)
58             {
59                 add(y % i, i, id[a[y - 1]], y, -1);
60                 add(y % i, i, id[ch], y, 1);
61             }
62             a[y - 1] = ch;
63         }
64         else 
65         {
66             scanf("%d %d %s", &y, &z, b);
67             int lenb = strlen(b);
68             int ans = 0;
69             for (int i = 0; i < lenb; i++)
70                 ans += query((y + i) % lenb, lenb, id[b[i]], z) - query((y + i)% lenb, lenb, id[b[i]], y - 1);
71             printf("%d\n", ans);
72         }
73     }
74     return 0;
75 }

View Code