loj #6092. 「Codeforces Round #418」恋爱循环

二分
 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<queue>
 6 #include<cmath>
 7 using namespace std;
 8 #define maxn 100000+15
 9 
10 int n,m,num,cnt,k;
11 char s[maxn],a,b,x;
12 int q[2333][2333];
13 char ch;
14 
15 inline void read(int &now)
16 {
17     int f=1; ch=getchar(); now=0;
18     while(ch>'9'||ch<'0') {if(ch=='-') f*=-1; ch=getchar();}
19     while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
20     now*=f;
21 }
22 
23 bool judge(int num)
24 {
25     int p=x-'a'+1;
26     for(int i=1;i<=n-num+1;i++)
27       if(q[p][i+num-1]-q[p][i-1]>=num-k) return false;
28     return true;
29 }
30 
31 int main()
32 {
33     read(n);
34     scanf("%s",s+1);
35     for(int i=1;i<=n;i++) 
36     {
37         for(int j=1;j<=26;j++)
38           q[j][i]=q[j][i-1];
39         q[s[i]-'a'+1][i]++;
40     }
41     read(m);
42     for(int i=1;i<=m;i++)
43     {
44         read(k);
45         scanf("%c",&x);
46         int l=0,r=n+1;
47         while(l+1<r)
48         {
49             int mid=(l+r)>>1;
50             if(judge(mid)) r=mid;
51             else l=mid;
52         }
53         printf("%d
",l);
54     }    
55     return 0;
56  }
View Code