【CF676C】Vasya and String(二分查找,线性扫描尺取法)

时间:2022-08-24 15:39:11

题意:

给出一个长度为n的字符串,只有字符'a'和'b'。最多能改变k个字符,即把'a'变成'b'或把'b'变成'a'。

问改变后的最长连续相同字符的字串长度为多少。

首先是二分查找,好想也好写

 var s:array[..]of longint;
ch:ansistring;
n,k,i,l,r,mid,last,ans:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; begin
//assign(input,'1.in'); reset(input);
//assign(output,'1.out'); rewrite(output);
readln(n,k);
readln(ch);
for i:= to n do
begin
s[i]:=s[i-];
if ch[i]='b' then inc(s[i]);
end;
ans:=;
for i:= to n do
begin
l:=i; r:=n; last:=i;
while l<=r do
begin
mid:=(l+r)>>;
if s[mid]-s[i-]<=k then begin last:=mid; l:=mid+; end
else r:=mid-;
end;
ans:=max(ans,last-i+);
end;
fillchar(s,sizeof(s),);
for i:= to n do
begin
s[i]:=s[i-];
if ch[i]='a' then inc(s[i]);
end;
for i:= to n do
begin
l:=i; r:=n; last:=i;
while l<=r do
begin
mid:=(l+r)>>;
if s[mid]-s[i-]<=k then begin last:=mid; l:=mid+; end
else r:=mid-;
end;
ans:=max(ans,last-i+);
end;
writeln(ans);
//close(input);
//close(output);
end.

然后是线性扫描,ACM叫做尺取法,机房大神叫伸头缩尾法

l循环后还要+1是因为要到下一段连续区间的开头,而当前连续间的字母和下一段一定不同(显然要找最长的连续相同序列),先默认将开头字母改好

 var ch:ansistring;
n,k,ans,r,l,i,t:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; begin
//assign(input,'1.in'); reset(input);
//assign(output,'1.out'); rewrite(output);
readln(n,k);
readln(ch);
l:=; r:=; t:=;
for i:= to n do
begin
if ch[i]='b' then
begin
if t<k then begin inc(t); inc(r); end
else
begin
while (l<=n)and(ch[l]='a') do inc(l);
inc(l);
inc(r);
end;
end
else inc(r);
ans:=max(ans,r-l);
end;
l:=; r:=; t:=;
for i:= to n do
begin
if ch[i]='a' then
begin
if t<k then begin inc(t); inc(r); end
else
begin
while (l<=n)and(ch[l]='b') do inc(l);
inc(l);
inc(r);
end;
end
else inc(r);
ans:=max(ans,r-l);
end;
writeln(ans);
//close(input);
//close(output);
end.