首页 > 代码库 > hdu 5056 Boring count
hdu 5056 Boring count
贪心算法。需要计算分别以每个字母结尾的且每个字母出现的次数不超过k的字符串,我们设定一个初始位置s,然后用游标i从头到尾遍历字符串,使用map记录期间各个字母出现的次数,如果以s开头i结尾的字符串满足要求,则把结果增加i-s+1。否则的话向前移动s,不断维护map,直到s指向的字母与i相同,从而满足字符串条件,把结果增加i-s+1。
需要注意的是结果可能会超int,需要用long long。
代码如下:
1 #define MAXS 100002 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstdio> 5 #include <cstring> 6 #include <map> 7 #include <vector> 8 #include <limits> 9 using namespace std;10 string s;11 int n;12 void solve()13 {14 map <char, int> mv;15 long long ans = 0;16 int start = 0;17 for( int i = 0 ; i < s.size() ; i++ )18 {19 if( mv.count(s[i]) == 0 )20 {21 mv[s[i]] = 1;22 ans += i - start + 1;23 }24 else if( mv[s[i]] < n )25 {26 mv[s[i]]++;27 ans += i -start + 1;28 }29 else30 {31 while( s[start] != s[i] )32 {33 mv[s[start]]--;34 start++;35 }36 start++;37 ans += i - start + 1;38 }39 }40 cout<<ans<<endl;41 }42 int main(int argc, char *argv[])43 {44 int T;45 scanf("%d", &T);46 while( T-- )47 {48 cin>>s;49 scanf("%d", &n);50 solve();51 }52 return 0;53 }
hdu 5056 Boring count
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。