Blackops

初心易得，始终难守

0%

HDU 5056 Boring count（尺取法）

发表于 分类于 ， ，

Boring count

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

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

题目链接：HDU 5056
发现尺取法很久没写了，便找了道题写写，显然所有子串要么是同一个起点，不同长度；要么是不同起点，不同长度，那么我们可以枚举起点，然后$O(n^2)$暴力地求，但是这样明显会超时，但是又可以发现对于每一个起点$i$，如果它最长合法区间能拓展到右边的$j$，那么显然以$i$为固定起点，$S_{i…j}$都是合法的，对答案的贡献就是这段最长区间的长度，那么就可以用尺取法计算所有的最长区间，累加贡献得到答案。
通过这题好像发现尺取法的一个适用条件：假设区间的一端端点不变，另一端缩短，这种影响应该使得答案区间可以向未拓展的区间增加，或无影响，否则某一端还要返回去寻找最合适的指针，就退化成$O(n^2)$的算法了。
代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
char s[N];
int buc[N];

int main(void)
{
    int TC;
    scanf("%d", &TC);
    while (TC--)
    {
        CLR(buc, 0);
        int k;
        scanf("%s%d", s, &k);
        int len = strlen(s);
        int l = 0, r = 0;
        LL ans = 0;
        while (l < len)
        {
            int temp = 0;
            while (r < len)
            {
                int v = s[r] - 'a';
                if (buc[v] + 1 <= k)
                {
                    ++buc[v];
                    ++r;
                    ++temp;
                }
                else
                    break;
            }
            ans += r - l;
            --buc[s[l++] - 'a'];
        }
        printf("%I64d\n", ans);
    }
    return 0;
}