【CF676C】Vasya and String（二分查找，线性扫描尺取法）

题意：

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

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

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

 1 var s:array[0..100000]of longint;
 2     ch:ansistring;
 3     n,k,i,l,r,mid,last,ans:longint;
 4 
 5 function max(x,y:longint):longint;
 6 begin
 7  if x>y then exit(x);
 8  exit(y);
 9 end;
10 
11 begin
12  //assign(input,'1.in'); reset(input);
13  //assign(output,'1.out'); rewrite(output);
14  readln(n,k);
15  readln(ch);
16  for i:=1 to n do
17  begin
18   s[i]:=s[i-1];
19   if ch[i]='b' then inc(s[i]);
20  end;
21  ans:=0;
22  for i:=1 to n do
23   begin
24   l:=i; r:=n; last:=i;
25   while l<=r do
26   begin
27    mid:=(l+r)>>1;
28    if s[mid]-s[i-1]<=k then begin last:=mid; l:=mid+1; end
29     else r:=mid-1;
30   end;
31   ans:=max(ans,last-i+1);
32  end;
33  fillchar(s,sizeof(s),0);
34  for i:=1 to n do
35  begin
36   s[i]:=s[i-1];
37   if ch[i]='a' then inc(s[i]);
38  end;
39  for i:=1 to n do
40   begin
41   l:=i; r:=n; last:=i;
42   while l<=r do
43   begin
44    mid:=(l+r)>>1;
45    if s[mid]-s[i-1]<=k then begin last:=mid; l:=mid+1; end
46     else r:=mid-1;
47   end;
48   ans:=max(ans,last-i+1);
49  end;
50  writeln(ans);
51  //close(input);
52  //close(output);
53 end.

View Code

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

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

 1 var ch:ansistring;
 2     n,k,ans,r,l,i,t:longint;
 3 
 4 function max(x,y:longint):longint;
 5 begin
 6  if x>y then exit(x);
 7  exit(y);
 8 end;
 9 
10 begin
11  //assign(input,'1.in'); reset(input);
12  //assign(output,'1.out'); rewrite(output);
13  readln(n,k);
14  readln(ch);
15  l:=1; r:=1; t:=0;
16  for i:=1 to n do
17  begin
18   if ch[i]='b' then
19   begin
20    if t<k then begin inc(t); inc(r); end
21     else
22     begin
23      while (l<=n)and(ch[l]='a') do inc(l);
24      inc(l);
25      inc(r);
26     end;
27   end
28    else inc(r);
29   ans:=max(ans,r-l);
30  end;
31  l:=1; r:=1; t:=0;
32  for i:=1 to n do
33  begin
34   if ch[i]='a' then
35   begin
36    if t<k then begin inc(t); inc(r); end
37     else
38     begin
39      while (l<=n)and(ch[l]='b') do inc(l);
40      inc(l);
41      inc(r);
42     end;
43   end
44    else inc(r);
45   ans:=max(ans,r-l);
46  end;
47  writeln(ans);
48  //close(input);
49  //close(output);
50 end.

View Code