基础模板
求和大于等于S的最小子段
ll sum=0;
int l=1,r=1;
while(true){
//全速推进r指针
while(r<=n && sum<s){
sum+=a[r++];
}
//r走到头,sum无法再增大,答案无法更优
if(sum<s){
break;
}
//更新答案
ans=min(ans,r-l);
//龟速推进l指针
sum-=a[l++];
}
例题
POJ3061
即上面模板题
HDU5672
题意
给定一个字符串,要求出不同字符个数大于等于k的子串个数。
分析
- 跟不同数/字母个数相关的也是常用到尺取法。
- 一样的套路,先全速推进r,字符出现次数计数并更新不同字符个数,然后累计答案,龟速推进l。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
char s[N];
int T,k;
int cnt[30];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--){
memset(cnt,0,sizeof(cnt));
scanf("%s",s+1);
scanf("%d",&k);
int n=strlen(s+1);
ll ans=0;
int num=0;
int l=1,r=1;
while(true){
while(r<=n && num<k){
cnt[s[r]-'a']++;
if(cnt[s[r]-'a']==1){
num++;
}
r++;
}
if(num<k){
break;
}
ans+=(n-(r-1)+1);
cnt[s[l]-'a']--;
if(cnt[s[l]-'a']==0){
num--;
}
l++;
if(l>r){
r=l+1;
}
}
printf("%lld\n",ans);
}
return 0;
}
HDU5056
题意
给定一个字符串,要求出串内所有字符出现次数都小于等于k的子串个数。
分析
- 同样是尺取法的思想,不过写法略微不同。
- \(cnt\)同样是维护当前区间每种字母的个数,全速推进\(r\),没加入一个字符\(s[r]\),如果\(cnt[s[r]-'a']<=k\),就直接累计答案,否则,删除该字符,\(r\)回退,然后推进\(l\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
char s[N];
int T,k;
int cnt[30];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--){
memset(cnt,0,sizeof(cnt));
scanf("%s",s+1);
scanf("%d",&k);
int n=strlen(s+1);
ll ans=0;
int l=1,r=1;
while(l<=n){
while(r<=n){
cnt[s[r]-'a']++;
if(cnt[s[r]-'a']<=k){
ans+=r-l+1;
r++;
}else{
cnt[s[r]-'a']--;
break;
}
}
cnt[s[l]-'a']--;
l++;
}
printf("%lld\n",ans);
}
return 0;
}