hdu 5056(尺取法思路题)

Boring count

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 932 Accepted Submission(s): 382

Problem Description

You are given a string S consisting of lowercase letters, and your task is counting the number of substring that the number of each lowercase letter in the substring is no more than K.

Input

In the first line there is an integer T , indicates the number of test cases.
For each case, the first line contains a string which only consist of lowercase letters. The second line contains an integer K.

[Technical Specification]
1<=T<= 100
1 <= the length of S <= 100000
1 <= K <= 100000

Output

For each case, output a line contains the answer.

Sample Input

3
abc
1
abcabc
1
abcabc
2

Sample Output

6
15
21

Source

BestCoder Round #11 (Div. 2)

题意:找出一个字符串里面符合每个字幕出现次数都不大于K次的子串的个数。

题解:数据量达到了10^5,所以O(n^2)肯定不行，所以要用到尺取法。

整个过程分为4布：

　　　　1.初始化左右端点

　　　　2.不断扩大右端点，直到满足条件

　　　　3.如果第二步中无法满足条件，则终止，否则更新结果

　　　　4.将左端点扩大1，然后回到第二步

尺取法的过程是上述，但是，对于这题，我们要做少许改动，因为尺取法的条件终止条件是无法满足条件，但是这题我们首先扩充右端点的话是一直到不满足条件(找到某个字母出

现次数大于K的那个串再break)，所以这题我们的条件应该改成r在外层循环，找到无法满足条件的子串后再一直扩充左端点，直到满足条件。接下来怎么算子串个数呢？我也不知道

，discuss区里面这样说的。。

队友的解释:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int Hash[N],k;
char str[N];
bool judge(){
    for(int i=0;i<26;i++){
        if(Hash[i]>k) return false;
    }
    return true;
}
int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--){
        scanf("%s",str);
        scanf("%d",&k);
        int len = strlen(str);
        memset(Hash,0,sizeof(Hash));
        int l=0,r=0;
        LL cnt=0;
        while(r<len){
            Hash[str[r]-'a']++;
            while(l<len&&!judge()){
                Hash[str[l]-'a']--;
                l++;
            }
            if(!judge()) break;
            //printf("%d %d
",l,r);
            cnt =cnt+(r-l+1);
            r++;
        }
        printf("%lld
",cnt);
    }
    return 0;
}