26个小写英文字母，1500的数组，询问输入的m<=n，那么，询问的可能是26*1500种可能，而题目给的q是20万，那么意味着有大量重复的数据，只要搜过的记忆一下，下次搜的时候直接输出就能过，当然也能暴力，先把26*1500次的可能暴力搜出来，用二维数组记录一下，然后询问的时候直接查找二维数组输出即可，过程艰辛是在不想说了，这里查找某一个字母的时候，我用到了尺取法，时间复杂度 26*1500*1500,218ms轻松过，
#include <iostream> #include<stdio.h> #include<algorithm> #include <string.h> #define maxn 300005 using namespace std; int n; char ss[1505]; int qu[26][1505]; int dp[1505],p[1505]; int tx[1505]; void solve(){ for(int i=0;i<26;i++){ for(int j=1;j<=n;j++){ int s=-1,curren=0; int maxx=0,zx=0; memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); int ans=j; for(int k=1;k<=n;k++){ //int pp; if(tx[k]==i){ dp[k]=dp[k-1]+1; }else{ if(ans>0){ --ans; dp[k]=dp[k-1]+1; p[zx]=k; if(s==-1) s=zx; ++zx; }else{ if(s==-1) dp[k]=0; else{ dp[k]=k-p[s]; p[zx]=k; ++zx; ++s; } } } if(dp[k]>maxx) maxx=dp[k]; } //cout<<char(i+'a')<<" "<<j<<"%%%"<<maxx<<endl; qu[i][j]=maxx; } } } int main() { while(~scanf("%d",&n)){ scanf("%s",ss+1); for(int i=1;i<=n;i++){ tx[i]=ss[i]-'a'; } //cout<<s[1]-'a'<<endl; solve(); int m; scanf("%d",&m); while(m--){ int d; char c; scanf("%d %c",&d,&c); printf("%d\n",qu[c-'a'][d]); } } return 0; }