MYF

HDU 5672 String

Posted on | In | | Visitors

题目链接

HDU 5672

BestCoder #81 1002 中文题面

解题方法：追赶法（尺取法,双指针法）

题目分析

题目大意

给定字符串，问有多少个子串，含有至少k个不同字母

解析

比赛的时候没做出来，显然是被C题的位置吓到了。实际上并不难，理清思路即可。

官方解析：

有一个明显的性质：如果子串(i,j)包含了至少k个不同的字符，那么子串(i,k),(j < k < length)也包含了至少k个不同字符。

因此对于每一个左边界，只要找到最小的满足条件的右边界，就能在O(1)时间内统计完所有以这个左边界开始的符合条件的子串。

寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，同时累加答案即可。复杂度 O(length(S))。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
char s[1000005];
int vis[130];
int main(){
    int t,n;
    scanf("%d",&t);
    for (int cas=1; cas<=t; cas++) {
        Memset(vis, 0);
        scanf("%s",s+1);
        scanf("%d",&n);
        int l=1,r=1,len=strlen(s+1),cnt=0;
        bool flag=false;
        ll ans=0;
        while (1) {
            while (cnt!=n) {
                if (r==len+1) {
                    flag=true;
                    break;
                }
                if (vis[s[r]]++==0) 
                    cnt++;
                r++;
            }
            if (flag) break;
            ans+=len-(r-1)+1;
            if (--vis[s[l]]==0) cnt--;
            l++;
        }
        printf("%lld\n",ans);
    }
}