AcWing 3175. 人物相关性分析(二分、双指针)
原题链接
简单
作者:
simoni
,
2022-02-25 23:12:38
,
所有人可见
,
阅读 339
二分
#include<bits/stdc++.h>
using namespace std;
char arr[1000010];
int k;
int arra[1000010];
int arrb[1000010];
long long ans;
bool checka(int i){
if((arr[i-1]>'z'||arr[i-1]<'A'||(arr[i-1]<'a'&&arr[i-1]>'Z'))&&(arr[i+5]>'z'||arr[i+5]<'A'||(arr[i+5]<'a'&&arr[i+5]>'Z'))&&arr[i]=='A'&&arr[i+1]=='l'&&arr[i+2]=='i'&&arr[i+3]=='c'&&arr[i+4]=='e')return 1;
return 0;
}
bool checkb(int i){
if((arr[i-1]>'z'||arr[i-1]<'A'||(arr[i-1]<'a'&&arr[i-1]>'Z'))&&(arr[i+3]>'z'||arr[i+3]<'A'||(arr[i+3]<'a'&&arr[i+3]>'Z'))&&arr[i]=='B'&&arr[i+1]=='o'&&arr[i+2]=='b')return 1;
return 0;
}
int main(){
scanf("%d\n",&k);
// gets(arr+1);
cin.getline(arr+1,1000008);
int ia=0;
int ib=0;
// arrb[ib++]=-10000000;
for(int i=1;i<1000010;i++){
if(checka(i)){
arra[ia]=i;
ia++;
}
if(checkb(i)){
arrb[ib]=i;
ib++;
}
}
// arrb[ib++]=10000000;
for(int i=0;i<ia;i++){
int l=0,r=ib-1,mid;
while(l<r){
mid=(l+r)>>1;
if(arrb[mid]>=arra[i]-3-k)r=mid;
else l=mid+1;
}
int ll=l;
r=ib;
while(l<r){
mid=(l+r)>>1;
if(arrb[mid]>k+arra[i]+5)r=mid;
else l=mid+1;
}
ans+=l-ll;
}
cout<<ans;
}
双指针
#include<bits/stdc++.h>
using namespace std;
char arr[1000010];
int k;
int arra[1000010];
int arrb[1000010];
long long ans;
bool checka(int i){
if((arr[i-1]>'z'||arr[i-1]<'A'||(arr[i-1]<'a'&&arr[i-1]>'Z'))&&(arr[i+5]>'z'||arr[i+5]<'A'||(arr[i+5]<'a'&&arr[i+5]>'Z'))&&arr[i]=='A'&&arr[i+1]=='l'&&arr[i+2]=='i'&&arr[i+3]=='c'&&arr[i+4]=='e')return 1;
return 0;
}
bool checkb(int i){
if((arr[i-1]>'z'||arr[i-1]<'A'||(arr[i-1]<'a'&&arr[i-1]>'Z'))&&(arr[i+3]>'z'||arr[i+3]<'A'||(arr[i+3]<'a'&&arr[i+3]>'Z'))&&arr[i]=='B'&&arr[i+1]=='o'&&arr[i+2]=='b')return 1;
return 0;
}
int main(){
scanf("%d\n",&k);
// gets(arr+1);
cin.getline(arr+1,1000008);
int ia=0;
int ib=0;
for(int i=1;i<1000010;i++){
if(checka(i)){
arra[ia]=i;
ia++;
}
if(checkb(i)){
arrb[ib]=i;
ib++;
}
}
for(int i=0,jl=0,jr=0;i<ia;i++){
while(arra[i]-arrb[jl]-3>k&&jl<ib-1)jl++;
while(arrb[jr]-arra[i]-5<=k&&jr<ib)jr++;
ans+=jr-jl;
}
cout<<ans;
}