首页 > 代码库 > hdu 5056 Boring count （类似单调队列的做法。。）
hdu 5056 Boring count （类似单调队列的做法。。）
给一个由小写字母构成的字符串S，问有多少个子串满足：在这个子串中每个字母的个数都不超过K。
数据范围：
1<=T<= 100
1 <= the length of S <= 100000
1 <= K <= 100000
思路：
考虑以S[i]结尾的子串，若以S[j] （j<i）作为头不能构成一个符合条件的子串，则S[1]...S[j]都不能作为子串的头。
若S[j+1]可以作为子串的头，则以S[i]结尾的符合条件的子串个数是i-j。
做法：单调队列的思想，不多解释，直接看代码。
代码：
#include <cstdio>#include <iostream>#include <string.h>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <map>#include <stack>using namespace std;int const uu[4] = {1,-1,0,0};int const vv[4] = {0,0,1,-1};typedef long long ll;int const maxn = 50005;int const inf = 0x3f3f3f3f;ll const INF = 0x7fffffffffffffffll;double eps = 1e-10;double pi = acos(-1.0);#define rep(i,s,n) for(int i=(s);i<=(n);++i)#define rep2(i,s,n) for(int i=(s);i>=(n);--i)#define mem(v,n) memset(v,(n),sizeof(v))#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1int T,k;char s[100005];int pq[100005];ll caseNum[200];ll b[100005];int main(){ cin>>T; while(T--){ scanf("%s",s); scanf("%d",&k); int L=strlen(s); int head=1, tail=0; mem(caseNum,0); mem(b,0); b[0]=1; pq[++tail]=s[0]-‘0‘; caseNum[pq[tail]]++; rep(i,1,L-1){ pq[++tail]=s[i]-‘0‘; caseNum[pq[tail]]++; if(caseNum[pq[tail]]>k){ do{ caseNum[pq[head]]--; ++head; }while(caseNum[pq[tail]]>k); } b[i]=tail-head+1; } ll ans=0; rep(i,0,L-1) ans+=b[i]; printf("%I64d\n",ans); }}
hdu 5056 Boring count （类似单调队列的做法。。）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。