hdu5056(找相同字母不出现k次的子串个数)

题意：
     给你一个字符串，然后问你这个字符串里面有多少个满足要求的子串，要求是每个子串相同字母出现的次数不能超过k。

思路：
     这种题目做着比较有意思，而且不是很难（但自己还是嘚瑟，wa了好几次），这个题目的关键就是时间问题，对于每一个字母，我们只要加上以他为结尾的满足要求的子串个数就行了，假如前面的字母出现个数都没有超过k，那么当前的可以增加的和就是之前所有的字母个数，如果当前的字母个数出现超过k了，那么就得更新起点now（这个起点就是自己作为标记可行的最前位置），ans += 当前到now的字母的个数，具体的细节看下面代码，我写个核心的部分。

int mark[] 表示的是当前可满足的区间中每个字母出现的次数

int now 表示的是当前可满足区间的最前端的下标
int now = 0;
for(int i = 0 ;i < n ;i ++)
{
    if(++mark[str[i]] > k)
    {
       int nowid = now;
       while(1)//这个别忘记了，一开始忘记了wa了好几次，挪动当前满足串的范围的时         {       //候记得挪动出去的部分的字母出现次数减出去。
          mark[str[nowid]] --;
          if(str[nowid] == str[i]) break;
          nowid ++;
       }
       now = nowid;
     }
     Ans += (i+1 - now);

}

#include<stdio.h> #include<string.h> char str[110000]; int mark[30];int main () {int n ,t ,k;__int64 Ans ,i ,now;scanf("%d" ,&t);while(t--){scanf("%s" ,str);scanf("%d" ,&k);n = strlen(str);Ans = now = 0;memset(mark ,0 ,sizeof(mark));for(i = 0 ;i < n ;i ++){if(++mark[str[i]-'a'] > k){int nowi = now;while(1){mark[str[nowi]-'a'] --;if(str[nowi] == str[i]) break;nowi ++;}now = nowi + 1;}Ans += (i - now + 1);}printf("%I64d\n" ,Ans);}return 0; }

总结

以上是生活随笔为你收集整理的hdu5056(找相同字母不出现k次的子串个数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。