題意：
? ? ?給你一個(gè)字符串，然后問你這個(gè)字符串里面有多少個(gè)滿足要求的子串，要求是每個(gè)子串相同字母出現(xiàn)的次數(shù)不能超過k。

思路：
? ? ?這種題目做著比較有意思，而且不是很難（但自己還是嘚瑟，wa了好幾次），這個(gè)題目的關(guān)鍵就是時(shí)間問題，對(duì)于每一個(gè)字母，我們只要加上以他為結(jié)尾的滿足要求的子串個(gè)數(shù)就行了，假如前面的字母出現(xiàn)個(gè)數(shù)都沒有超過k，那么當(dāng)前的可以增加的和就是之前所有的字母?jìng)€(gè)數(shù)，如果當(dāng)前的字母?jìng)€(gè)數(shù)出現(xiàn)超過k了，那么就得更新起點(diǎn)now（這個(gè)起點(diǎn)就是自己作為標(biāo)記可行的最前位置），ans += 當(dāng)前到now的字母的個(gè)數(shù)，具體的細(xì)節(jié)看下面代碼，我寫個(gè)核心的部分。

int mark[] 表示的是當(dāng)前可滿足的區(qū)間中每個(gè)字母出現(xiàn)的次數(shù)

int now 表示的是當(dāng)前可滿足區(qū)間的最前端的下標(biāo)
int now = 0;
for(int i = 0 ;i < n ;i ++)
{
? ? if(++mark[str[i]] > k)
? ? {
? ? ? ?int nowid = now;
? ? ? ?while(1)//這個(gè)別忘記了，一開始忘記了wa了好幾次，挪動(dòng)當(dāng)前滿足串的范圍的時(shí) ? ? ? ? { ? ? ? //候記得挪動(dòng)出去的部分的字母出現(xiàn)次數(shù)減出去。
? ? ? ? ? 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; }

總結(jié)

以上是生活随笔為你收集整理的hdu5056(找相同字母不出现k次的子串个数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。