首页 > 代码库 > hdu 5056 Boring count

hdu 5056 Boring count

2024-07-25 00:37:50   228人阅读

贪心算法。需要计算分别以每个字母结尾的且每个字母出现的次数不超过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


联系
我们