hdu 5056 所有字母数都<=k的子串数目

<a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=5056" style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">http://acm.hdu.edu.cn/showproblem.php?pid=5056</a>

所有字母个数都不超过k的字串数目

比赛时候用模拟+组合数学过的，是O(2*26*N)的复杂度，但是没有正解快

遍历每个恰好符合条件的[i,j]，其中若包含[i,jj]其中jj是上次计数的最远的j，就+一次i~j -一次i~jj

过的比较险

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include<set>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

LL gcd(LL a,LL b){    return b == 0? a:gcd(b,a%b);}

char s[100005];

int n,k;

LL ans;

int cnt[26][100005];

void work()

{

    //clr0(cnt);

    scanf("%s",s);

    RD(k);

    n = strlen(s);

    for(int i = 0;i < 26;++i)

        memset(cnt[i],0,sizeof(int)*(n+1));

    ans = 0;

    for(int i = 1;i <= n;++i){

        for(int l = 0;l < 26;++l){

            cnt[l][i] = cnt[l][i-1];

        }

        cnt[s[i - 1] - 'a'][i]++;

    }

    int mx;

    for(int i = 0,j = 1,jj = 0;i <= n;++i){

        while(j <= n){

            mx = 0;

            for(int l = 0;l < 26;++l){

                mx = max(mx,cnt[l][j] - cnt[l][i]);

            }

            if(mx > k)

                break;

            ++j;

        }

        if(j == jj)

            continue;

        if(mx > k){

            ans += 1LL*(j-i)*(j-i-1)/2;

            if(jj > i)

                ans -= 1LL*(jj-i)*(jj-i-1)/2;

            jj = j;

            //cout<<ans<<endl;

        }

        else if(j > n){

            ans += 1LL*(n-i)*(n-i+1)/2;

            if(jj > i)

                ans -= 1LL*(jj-i)*(jj-i-1)/2;

            break;

        }

    }

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

}

int main() {

    int _;

    RD(_);

    while(_--){

        work();

    }

    return 0;

}

正解果然要快很多

枚举字符串下标i，每次计算以i为结尾的符合条件的最长串。那么以i为结尾的符合条件子串个数就是最长串的长度。求和即可。

计算以i为结尾的符合条件的最长串两种方法：

1.维护一个起点下标startPos，初始为1。如果当前为i，那么cnt[str[i]]++，如果大于k的话，就while( str[startPos] != str[i] ) cnt[str[startPos]]--, startPos++; 每次都保证 startPos~i区间每个字母个数都不超过k个。ans += ( i-startPos+1 )。 时间复杂度O(n)

2.预处理出所有字母的前缀和。然后通过二分找出以i为结尾的符合条件的最长串的左边界。时间复杂度O(nlogn)，写的不够好的可能超时。

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include<map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

char s[100005];

int n,k;

LL ans;

int cnt[256];

void work()

{

    scanf("%s",s+1);

    RD(k);

    n = strlen(s+1);

    clr0(cnt);

    ans = 0;

    int st = 1;

    for(int i = 1;i <= n;++i){

        cnt[s[i]]++;

        if(cnt[s[i]] > k){

            while(1){

                cnt[s[st]]--,st++;

                if(s[st-1] == s[i])

                    break;

            }

        }

        ans += i - st + 1;

    }

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

}

int main() {

    int _;

    RD(_);

    while(_--){

        work();

    }

    return 0;

}