hdu 5056 Boring count

http://acm.hdu.edu.cn/showproblem.php?pid=5056

题意：给你一个字符串，然后找出子串中每一个字母出现次数小于等于k的个数。

思路：枚举字符串下标i，每次计算以i为结尾的符合条件的最长串。那么以i为结尾的符合条件子串个数就是最长串的长度。求和即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 #define ll long long
 6 using namespace std;
 7 
 8 int n,m,t,k;
 9 char str[maxn];
10 int num[maxn];
11 
12 int main()
13 {
14     scanf("%d",&t);
15     while(t--)
16     {
17         memset(num,0,sizeof(num));
18         scanf("%s",str);
19         scanf("%d",&k);
20         int k1=strlen(str);
21         int pos=0;
22         ll ans=0;
23         for(int i=0; i<k1; i++)
24         {
25             num[str[i]-'a']++;
26             if(num[str[i]-'a']>k)
27             {
28                 while(str[pos]!=str[i])
29                 {
30                     num[str[pos]-'a']--;
31                     pos++;
32                 }
33                 num[str[pos]-'a']--;
34                 pos++;
35             }
36             ans+=(i-pos+1);
37         }
38         printf("%I64d
",ans);
39     }
40     return 0;
41 }

View Code