题解 | #科学家的模型#
音乐家的曲调
https://ac.nowcoder.com/acm/contest/11175/B
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;
}
查看5道真题和解析
投递字节跳动等公司8个岗位
腾讯成长空间 5981人发布