BestCoder Round #81 (div.2)C String

总体思路好想，就是在找K个不同字母的时候，卡时间。

看了大神代码，发现goto的！！！！998ms

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<queue>
 6 #include<stack>
 7 #include<cmath>
 8 #include<algorithm>
 9 #include<malloc.h>
10 using namespace std;
11 #define clc(a,b) memset(a,b,sizeof(a))
12 #define inf 0x3f3f3f3f
13 const int N=10010;
14 #define LL long long
15 const double eps = 1e-5;
16 const double pi = acos(-1);
17  int g[1010][1010];
18 inline int r(){
19     int x=0,f=1;char ch=getchar();
20     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
22     return x*f;
23 }
24 int num[30];
25 int jude(){
26     int ans=0;
27     for(int i=0;i<27;i++){
28         ans+=(num[i]!=0);
29     }
30     return ans;
31 }
32 char s[1000010];
33 int main(){
34     int T,k;
35     scanf("%d",&T);
36     while(T--){
37         clc(num,0);
38         scanf("%s",s+1);
39         scanf("%d",&k);
40         int len=strlen(s+1);
41         int j=0;
42         LL ans=0;
43         for(int i=1;i<=len;i++){
44                while(jude()!=k){
45                     j++;
46                     if(j>len) goto l;
47                     num[s[j]-'a']++;
48                }
49                if(j>len) break;
50                num[s[i]-'a']--;
51                ans+=len-j+1;//这样每次枚举K个不同的字符串，不会有覆盖的情况
52         }
53         l:;
54         printf("%I64d
",ans);
55     }
56     return 0;
57 }

View Code

优化代码180ms：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<queue>
 6 #include<stack>
 7 #include<cmath>
 8 #include<algorithm>
 9 #include<malloc.h>
10 using namespace std;
11 #define clc(a,b) memset(a,b,sizeof(a))
12 #define inf 0x3f3f3f3f
13 const int N=10010;
14 #define LL long long
15 const double eps = 1e-5;
16 const double pi = acos(-1);
17  int g[1010][1010];
18 inline int r(){
19     int x=0,f=1;char ch=getchar();
20     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
22     return x*f;
23 }
24 char s[1000010];
25 LL ans;
26 int a[30];
27 int main(){
28     int T;
29     scanf("%d",&T);
30     while(T--){
31         clc(a,0);
32         scanf("%s",s+1);
33         int len=strlen(s+1);
34         int k;
35         ans=0;
36         scanf("%d",&k);
37         if(k==1){
38             ans=((len+1)*len)/2;
39             printf("%I64d
",ans);
40             continue;
41         }
42         for(int i=0;i<26;i++){
43             a[i]=0;
44         }
45         int l=0;
46         int j=1;
47         for(int i=1;i<=len;i++){
48             if(a[s[i]-'a']==0){
49                  a[s[i]-'a']++;
50                  l++;
51             }
52             else 
53                 a[s[i]-'a']++;
54             if(l>=k){
55                 ans+=len-i+1;
56                 for(;j<i;j++){
57                     a[s[j]-'a']--;
58                     if(a[s[j]-'a']==0){
59                         l--;
60                         j++;
61                         break;
62                     }
63                     else{
64                         ans+=len-i+1;
65                     }
66                 }
67             }
68         }
69         printf("%I64d
",ans);
70     } 
71     return 0;
72 }

View Code