首页 > 代码库 > Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection(双指针)

Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection(双指针)

2024-10-12 19:00:02   214人阅读

题目链接：Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection

题意：

给你一个字符串，有q个询问，每个询问一个x和一个字符 o。

现在让你在原来的字符串上最多改变x个字符，问能构成最长的o子串的长度。

题解：

一共有26*1500种状态，对于每个状态用双指针滚一滚就行了。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 const int N=1507;
 6 int ans[27][N],n,k,x;
 7 char s[N],o[2];
 8 
 9 int del(int i,int j)
10 {
11     int ans=0;
12     for(int l=1,r=1,cnt=0;r<=n;r++)
13     {
14         cnt+=s[r]!=j;
15         if(cnt<=i)ans=max(ans,r-l+1);
16         while(l<=r&&cnt==i+1)cnt-=s[l]!=j,l++;
17     }
18     return ans;
19 }
20 
21 int main(){
22     scanf("%d%s",&n,s+1);
23     F(i,1,n)s[i]-=‘a‘;
24     F(i,0,25)F(j,1,n)ans[i][j]=del(j,i);
25     scanf("%d",&k);
26     while(k--)
27     {
28         scanf("%d%s",&x,o),o[0]-=‘a‘;
29         printf("%d\n",ans[*o][x]);
30     }
31     return 0;
32 }
View Code

 

Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection(双指针)


联系
我们