题解 | #科学家的模型#

B题

思路分析

题意：选三个互不相交的满足条件的区间，问这三个区间的长度之和最大是多少？
使用方法：尺取法（双指针）

思路如下：
不妨令三个区间为 左边的区间:A，中间的区间:B，右边的区间:C
令 res 为 三个区间的长度之和的最大值

我们枚举中间的区间:B         
假设B区间的范围为[l,r]，则对于该区间而言 le[l-1] + r-l+1 + ri[r+1] 为res
ps ：
le[i]: 区间[1,i] 内 满足条件的一个区间的最大长度
ri[i]: 区间[i,n] 内 满足条件的一个区间的最大长度

若共枚举到 num 个 B 区间，对于每一个 B 区间 我们会得到一个 res_i  // i的范围区间为 [1,num] 
则 最终的res = max(res_1,res_2,...,res_num) 

所以我们的思路是这样的：先求出 le[]数组 和 ri[] 数组 再 枚举B区间 求得 res

综上：Code 如下.

Code

#include <bits/stdc++.h>

using namespace std;

const int N=1e7+10;

int le[N],ri[N];
int cnt[26];  // 记录各个字母的出现次数
char s[N];
int n,m;

int main(){
    cin>>n>>m;
    cin>>s+1;

    // 求 le数组
    for(int i=1,j=1;j<=n;j++){
        cnt[s[j]-'a']++;
        while(cnt[s[j]-'a']>m&&i<=j) cnt[s[i]-'a']--,i++;
        le[j]=max(le[j-1],j-i+1);
    }

    // 求 ri数组
    memset(cnt,0,sizeof cnt);
    for(int i=n,j=n;i>=1;i--){
        cnt[s[i]-'a']++;
        while(cnt[s[i]-'a']>m&&i<=j) cnt[s[j]-'a']--,j--;
        ri[i]=max(ri[i+1],j-i+1);
    }

    // 枚举B区间 得到res 
     int res=-1;
     memset(cnt,0,sizeof cnt);
     for(int i=1,j=1;j<=n;j++){
        cnt[s[j]-'a']++;
        while(cnt[s[j]-'a']>m&&i<=j) cnt[s[i]-'a']--,i++;
        res=max(res,le[i-1]+j-i+1+ri[j+1]);
    }

    cout<<res<<endl;

    return 0;
}