hdu 5672 尺取还是挺好用的

先简单介绍下尺取法

http://blog.chinaunix.net/uid-24922718-id-4848418.html

尺取法就是在卡给定条件的时候 不断的改变下标 起点 终点

#include<cstdio>

#include<iostream>

#include<string.h>

using namespace std;

int main()

{

    int t,k,j,vis[];

    char a[];

    cin>>t;

    while(t--)

    {

        scanf("%s",&a);

        scanf("%d",&k);

        int l=,temp,num=,i=;

        long long int ans=;

        memset(vis,,sizeof(vis));

        int len=strlen(a);

        while(l<=i&&l<len)

        {

            while(i<len&&num<k)

           {

                temp=a[i++]-'a';

                if(vis[temp]==) num++;

                vis[temp]++;

           }

           if(num<k) break;

           ans+=(len-i+);

           temp=a[l]-'a';

           vis[temp]--;

           if(vis[temp]==) num--;

           l++;

        }

        printf("%I64d\n",ans);

    }

    return;

}

 

最后就这道题目来说说吧 两个点吧

1.这里的要求是不同的字母数 可以用标记数组实现（注意在挪起点的时候 要对标记数组进行处理）

2.题目要求的是所有subquence的个数那么 在爬出最简单的时候 后面的一些就是需要增加的