题目地址:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=691&pid=1003
题意:找出一个字符串满足至少有k个不相同的字母的字串的个数
可以注意到 如果 i到j 是满足条件的 则 i到j+1,j+2...n都是满足的,所以可以用尺取法,每次找到满足条件最短的 i,j 然后每次都加上 n-j+1就是答案
#include<bits/stdc++.h> #define inf 0x3f3f3f3f const int maxn=1000000; using namespace std; int t,k,len,sum; __int64 ans; char a[maxn+10],flag[maxn+10]; int main() { scanf("%d",&t); for(int h=1;h<=t;h++){ memset(flag,0,sizeof(flag)); scanf("%s%d",a,&k); len=strlen(a); // printf("%d\n",len); int head=0,tail=0,sum=0; ans=0; for(;;){ while(head<len&&sum<k){ if(!flag[a[head]-'A']) { sum++; } flag[a[head]-'A']++; head++; // printf("1\n"); } if(sum<k) break; ans+=(len-head+1); //printf("%I64d\n",ans); while(tail<head&&sum>=k){ if(flag[a[tail]-'A']) { flag[a[tail]-'A']--; if(!flag[a[tail]-'A']) sum--; } if(sum>=k) ans+=(len-head+1); tail++; } // printf("%d\n",head); } printf("%I64d\n",ans); } return 0; }