思维定势太强，脑洞不够大囧

原题：

 

 

n<=5e6，k<=10 

 

第一眼看：26进制表示连续的k个碱基，由于k能到10所以离散化一下

一看数据：n是5e6？？？这离散化必然会被卡

思考一下：会不会是loj跑太快了出题人要卡做法才出这么极限

我觉得不太可能，就没去写，怎么都想不到做法

第二天：字母只有四种，可能的连续碱基只有1e6种。。。。。。

这种题也不难，就是注意到碱基只有四种就行

但是就是注意不到，思维定势太强

这还打个P啊怎么办啊怎么办啊怎么办啊怎么办啊怎么办啊怎么办啊怎么办啊啊啊啊啊

 

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char s[5100000];
 6 int a[5100000],n,m;
 7 int cnt[2100000];
 8 int main(){
 9     scanf("%s",s+1);
10     n=strlen(s+1);
11     scanf("%d",&m);
12     for(int i=1;i<=n;++i){
13         if(s[i]=='A')  a[i]=0;
14         else if(s[i]=='G')  a[i]=1;
15         else if(s[i]=='T')  a[i]=2;
16         else if(s[i]=='C')  a[i]=3;
17     }
18     int up=(1<<(m*2-2));
19     int tmp=0;
20     for(int i=1;i<m;++i)
21         tmp=((tmp<<2)|a[i]);
22     int ans=0;
23     for(int i=m;i<=n;++i){
24         tmp=(((tmp%up)<<2)|a[i]);
25         cnt[tmp]++;
26         ans=max(ans,cnt[tmp]);
27     }
28     printf("%d\n",ans);
29     return 0;
30 }

View Code