Good Substrings

?CodeForces - 271D?

給你一個只包含小寫字母的字符串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 5 樣例輸入2 acbacbacaa
00000000000000000000000000
2 樣例輸出2 8

樣例解釋對于第一個樣例,符合要求的子串分別為:"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('\n') 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 5Input acbacbacaa 00000000000000000000000000 2 Output 8input 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('\n') 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 5Input acbacbacaa 00000000000000000000000000 2 Output 8 */ View Code

?

轉載于:https://www.cnblogs.com/gaojunonly1/p/11148216.html

總結

以上是生活随笔為你收集整理的codeforces271D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。