codeforces271D

Good Substrings

给你一个只包含小写字母的字符串s.
问你在这个字符串中有多少个不同的子串.
且要求这些子串中不得出现超过k个的特殊字母.
*子串s1和子串s2不同,当且仅当s1!=s2,即s1和s2完全不同.
*子串指的是字符串中截取出来的连续的一段.
输入格式第一行,一个长度不超过1500仅包含小写字母的字符串s.
第二行,包含一个长度为26的01字符串,如果字符串的第i(0<=i< length(s))个位置为'0',说明'a'+i为特殊字母,否则'a'+i不是特殊字母.
第三行,包含一个整数k(0<=k<=|s|).输出格式只有一个整数,表示符合要求的不同子串的个数样例

样例输入1

ababab
01000000000000000000000000
1

样例输出1

样例输入2

acbacbacaa
00000000000000000000000000
2

样例输出2

样例解释对于第一个样例,符合要求的子串分别为:"a", "ab", "b", "ba", "bab".

sol：DIV2的D嘛，直接n²暴力搞出所有子串，然后一开始用set去重，T到怀疑人生，然后用哈希，又WA到死

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=1505;
int n,m,No[N];
string S,Spe;
bool Bo[30];
set<string>Ans;
int main()
{
    freopen("data.in","r",stdin);
//    freopen("my.out","w",stdout);
    int i,j;
    cin>>S; n=S.size(); S='$'+S;
    cin>>Spe; for(i=0;i<26;i++) if(Spe[i]=='0') Bo[i]=1;
    R(m);
    for(i=1;i<=n;i++) if(Bo[S[i]-'a']) No[i]=1;
    for(i=2;i<=n;i++) No[i]+=No[i-1];
    Ans.clear();
    for(i=1;i<=n;i++) for(j=i;j<=n;j++)
    {
        if(No[j]-No[i-1]>m) break;
        else
        {
            string t; t=S.substr(i,j-i+1); Ans.insert(t);
        }
    }
//    set<string>::iterator it;
//    for(it=Ans.begin();it!=Ans.end();it++) cout<<*it<<endl;
    Wl((int)(Ans.size()));
    return 0;
}
/*
Input
ababab
01000000000000000000000000
1
Output
5

Input
acbacbacaa
00000000000000000000000000
2
Output
8

input
kqdwdulmgvugvbl
00101010100100100101101110
13
output
114
*/

set（TLE）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=1505;
const ll Mod=2333333;
int n,m,Qzh[N];
unsigned long long a[N*N];
char S[N],Sp[30];
bool Bo[30];
int main()
{
    int i,j;
    scanf("%s",S+1); n=strlen(S+1);
    scanf("%s",Sp+1); for(i=1;i<=26;i++) if(Sp[i]=='0') Bo[i-1]=1;
    R(m);
    for(i=1;i<=n;i++) {if(Bo[S[i]-'a']) Qzh[i]=1; Qzh[i]+=Qzh[i-1];}
    *a=0;
    for(i=1;i<=n;i++)
    {
        unsigned long long tmp=0;
        for(j=i;j<=n;j++)
        {
            if(Qzh[j]-Qzh[i-1]>m) break;
            tmp=tmp*Mod+S[j]; a[++*a]=tmp;
        }
    }
    sort(a+1,a+*a+1);
    *a=unique(a+1,a+*a+1)-a-1;
    Wl((ll)(*a));
    return 0;
}
/*
Input
ababab
01000000000000000000000000
1
Output
5

Input
acbacbacaa
00000000000000000000000000
2
Output
8
*/

View Code