CF 676C

• 大水题，双端队列搞一发。$n<10^5$
  
  • 题意：对一个只有ab的串修改k个字符，使得其连续的字母个数最多。
  • 思路：记录每个字母个数的前缀和，求前缀和差值小于等于k的最远的一对就好。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 200007;
char str[maxn];
int pre[maxn][2], n, k;
int cal(int st)
{
    int l = 1, ret = 0;
    for(int r = 1; r <= n; r ++){
        while(l <= n && pre[r][st] - pre[l - 1][st] > k) l++;
        ret = std::max(ret, r - l + 1);
    }
    return ret;
}
int main()
{
    std::cin >> n >> k;
    std::cin >> str + 1;
    int ans = k;
    int coa = 0, cob = 0;
    for(int i = 1; i <= n; i ++){
        if(str[i] == 'a') coa ++;
        else cob ++;
        pre[i][0] = coa;
        pre[i][1] = cob;
    }
    ans = std::max(cal(0), cal(1));
    std::cout << ans << std::endl;
}