首页 > 代码库 > BestCoder11(Div2) 1003 Boring count (hdu 5056) 解题报告
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）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 typedef __int64 LL; 9 const int N = 1e5 + 2;10 const int maxn = 26 + 2;11 12 char s[N];13 int cnt[maxn];14 15 int main()16 {17 int T, k;18 #ifndef ONLINE_JUDGE19 freopen("in.txt", "r", stdin);20 #endif // ONLINE_JUDGE21 22 while (scanf("%d", &T) != EOF)23 {24 while (T--)25 {26 scanf("%s", s);27 scanf("%d", &k);28 memset(cnt, 0, sizeof(cnt));29 int len = strlen(s);30 int j = 0, startpos = 0;31 LL ans = 0;32 33 for (int j = 0; j < len; j++)34 {35 cnt[s[j]-‘a‘]++;36 while (cnt[s[j]-‘a‘] > k)37 {38 cnt[s[startpos]-‘a‘]--;39 startpos++;40 }41 ans += j - startpos + 1;42 }43 printf("%I64d\n", ans);44 }45 }46 return 0;47 }
BestCoder11(Div2) 1003 Boring count (hdu 5056) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。