hdu 5672

Contents

1. hdu 5672
2. 题目：
3. Input：
4. Output：
5. Sample Input
6. Sample Output
7. 题目大意：
8. 分析：
1. 8.1. 我做的时候遇到的问题：

题目：

There is a string S.S only contain lower case English character.(10≤length(S)≤1,000,000)
How many substrings there are that contain at least k(1≤k≤26) distinct characters?

Input：

There are multiple test cases. The first line of input contains an integer T(1≤T≤10) indicating the number of test cases. For each test case:

The first line contains string S.
The second line contains a integer k(1≤k≤26).

Output：

For each test case, output the number of substrings that contain at least k dictinct characters.

Sample Input

2
abcabcabca
4
abcabcabcabc
3

Sample Output

0
55

题目大意：

有一个 10≤长度≤1,000,000 的字符串，仅由小写字母构成。求有多少个子串，包含有至少k(1≤k≤26)个不同的字母？

分析：

尺取法

我做的时候遇到的问题：

ans += len - j + 1;当前的状态已经满足，后面的元素可以构成的集合2^n - 1，为什么不是再加后面元素可构成的集合个数？

答：子串是连续的，所以不能向上面想的那样，上面那个考虑的是子序列的情况，那么尺取法也就不行了，尺取法也是在连续的基础上的



#include <cstdio>
#include <cstring>

const int MAXN = 1000010;

int mark[26];
char str[MAXN];

int main()
{
    int T, k;
    scanf("%d", &T);
    while(T--){
        int flag = 0;
        long long ans = 0;
        memset(mark, 0, sizeof(mark));
        scanf("%s%d", str, &k);
        int len = strlen(str);
        int i = 0, j = 0;
        while(1){
            while(j < len && flag < k){
                if(!mark[str[j] - 'a'])
                    flag++;
                ++mark[str[j] - 'a'];
                ++j;
            }
            if(flag < k)//如果已经超界了就退出
                break;
            ans += len - j + 1;//前面这部分满足了那么加上后面的情况，因为j的基数是0,len的基数是1，所以加1
            --mark[str[i] - 'a'];
            if(!mark[str[i] - 'a'])
                --flag;
            ++i;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}