Steven_MengのBlog

模拟赛一开始的时候以为有$26$个英文字母,想了半天。。。
后来发现只有$4$个字母$\rm A,T,C,G$,就发现这题水了。
因为$4^{10}=1048576$数组能开的下,考虑把每$k$个字母装压在一个$\rm int$里面
我们就得到了一种$O(nk)$的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define MAXN 5000005
#define MAXM 1050000
using namespace std;
char ch[MAXN];
int cnt[MAXN];
const int val[26]={0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0};
//打一个表 A:0 T:1 C:2 G:3
const char st[4]={'A','T','C','G'};
int main(){
int n=0;
while (true){
char c=getchar();
if (c=='\n') break;
else ch[++n]=c;
}
int k;
scanf("%d",&k);
for (register int i=1;i<=n-k+1;++i){
int ans=0;
for (register int j=i;j<=i+k-1;++j){
ans=ans*4+val[ch[j]-'A'];
}
cnt[ans]++;
}
int maxn=0;
for (register int i=0;i<MAXM;++i){
if (cnt[i]>maxn) maxn=cnt[i];
}
printf("%d\n",maxn);
}

后来发现还有一种$O(n)$的做法:发现这个求哈希的过程类似于一个滑动窗口,每次取出最前的数,加入末尾的数。
于是只用考虑这两个移动就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define MAXN 5000005
#define MAXM 1050000
using namespace std;
int ch[MAXN],cnt[MAXN];
const int val[26]={0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0};
int main(){
int n=0;
while (true){
char c=getchar();
if (c=='\n') break;
else ch[++n]=val[c-'A'];
}
int k;
scanf("%d",&k);
int now=0;
int pw=1;
for (register int i=1;i<=k;++i){
now=now*4+ch[i];
pw*=4;
}
cnt[now]++;
for (register int i=2;i<=n-k+1;++i){
now-=ch[i-1]*pw/4;
now*=4;
now+=ch[i+k-1];
cnt[now]++;
}
int maxn=0;
for (register int i=0;i<MAXM;++i){
if (cnt[i]>maxn) maxn=cnt[i];
}
printf("%d\n",maxn);
}

话说也没比$O(nk)$快多少

 评论