BestCoder Round #81 (div.2)C String
生活随笔
收集整理的這篇文章主要介紹了
BestCoder Round #81 (div.2)C String
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
總體思路好想，就是在找K個(gè)不同字母的時(shí)候，卡時(shí)間。
看了大神代碼，發(fā)現(xiàn)goto的！！！！998ms
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
#include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
#define LL long long
const double eps = 1e-;
const double pi = acos(-);
int g[][];
inline int r(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int num[];
int jude(){
int ans=;
for(int i=;i<;i++){
ans+=(num[i]!=);
}
return ans;
}
char s[];
int main(){
int T,k;
scanf("%d",&T);
while(T--){
clc(num,);
scanf("%s",s+);
scanf("%d",&k);
int len=strlen(s+);
int j=;
LL ans=;
for(int i=;i<=len;i++){
while(jude()!=k){
j++;
if(j>len) goto l;
num[s[j]-'a']++;
}
if(j>len) break;
num[s[i]-'a']--;
ans+=len-j+;//這樣每次枚舉K個(gè)不同的字符串，不會有覆蓋的情況
}
l:;
printf("%I64d\n",ans);
}
return ;
}
優(yōu)化代碼180ms：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
#include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
#define LL long long
const double eps = 1e-;
const double pi = acos(-);
int g[][];
inline int r(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
char s[];
LL ans;
int a[];
int main(){
int T;
scanf("%d",&T);
while(T--){
clc(a,);
scanf("%s",s+);
int len=strlen(s+);
int k;
ans=;
scanf("%d",&k);
if(k==){
ans=((len+)*len)/;
printf("%I64d\n",ans);
continue;
}
for(int i=;i<;i++){
a[i]=;
}
int l=;
int j=;
for(int i=;i<=len;i++){
if(a[s[i]-'a']==){
a[s[i]-'a']++;
l++;
}
else
a[s[i]-'a']++;
if(l>=k){
ans+=len-i+;
for(;j<i;j++){
a[s[j]-'a']--;
if(a[s[j]-'a']==){
l--;
j++;
break;
}
else{
ans+=len-i+;
}
}
}
}
printf("%I64d\n",ans);
}
return ;
}
總結(jié)
以上是生活随笔為你收集整理的BestCoder Round #81 (div.2)C String的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Scratch第四十九讲：完美的下落和反
- 下一篇： .net(C#)常见面试题