Codeforces Round #354 (Div. 2)_Vasya and String(尺取法)

题目连接:http://codeforces.com/contest/676/problem/C

题意:一串字符串,最多改变k次,求最大的相同子串

题解:很明显直接尺取法

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#define cl(a,b) memset(a,b,sizeof(a));
#define FFC(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define LL long long
#define dbg puts("ok")
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
char a[];
int main(){
int n,k;
while(~scanf("%d%d",&n,&k)){
scanf("%s",a);
int l=,r=,ans=,ca=,cb=,tmp=;
while(r<n){
while(r<n&&tmp<=k){
if(a[r]=='a')ca++;else cb++;
tmp=min(ca,cb);
r++;
}
if(r==n&&tmp<=k){ans=max(r-l,ans);break;}
r--;if(a[r]=='a')ca--;else cb--;tmp=min(ca,cb);
ans=max(r-l,ans);
while(a[l]==a[l+]){if(a[l]=='a')ca--;else cb--;l++,tmp=min(ca,cb);}
if(a[l]=='a')ca--;else cb--;l++,tmp=min(ca,cb);
}
printf("%d\n",ans);
}
return ;
}
上一篇:XML学习笔记


下一篇:SQL SERVER XML 学习总结