BestCoder11(Div2) 1003 Boring count (hdu 5056) 解题报告

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5056

题目意思：给出一条只有小写字母组成的序列S，问当中可以组成多少条每个字母出现的次数 <= k 的子序列。

常规方法就是两重 for 循环暴力，很不幸的是，容易想到的方法往往会导致——TLE，恭喜～～

所以必须要想出一条特别的方法来处理，将两重循环降到一重！（这个方法我是看题解啦）

有两个指针：startpos 和 i 。含义表示从数组下标 startpos 到 i 中可以组成的最长符合条件的序列的开始点和结束点。其次，要有一个cnt数组，用来统计 startpos 到 i 中每个出现的次数，如果当前处理的数组下标 i 所表示的字母 > k，startpos 要往后移动，并且cnt[s[startpos]-'a']--。其实出现这种情况无非就是 s[startpos] == s[i] 了，直到cnt[s[i]-'a'] <= k 跳出循环，此时最长序列数为 i - startpos + 1，不断累加就是答案。时间复杂度为O(n)，因为整个序列的处理一直是向后处理的，没有回溯。

（代码中的 j 就是上面说的 i）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 const int N = 1e5 + ;

 const int maxn =  + ;

 char s[N];

 int cnt[maxn];

 int main()

 {

     int T, k;

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             scanf("%s", s);

             scanf("%d", &k);

             memset(cnt, , sizeof(cnt));

             int len = strlen(s);

             int j = , startpos = ;

             LL ans = ;

             for (int j = ; j < len; j++)

             {

                 cnt[s[j]-'a']++;

                 while (cnt[s[j]-'a'] > k)

                 {

                     cnt[s[startpos]-'a']--;

                     startpos++;

                 }

                 ans += j - startpos + ;

             }

             printf("%I64d\n", ans);

         }

     }

     return ;

 }