AcWing 3175. 人物相关性分析
原题链接
简单
作者:
曦薇
,
2022-04-05 21:57:05
,
所有人可见
,
阅读 203
思路
- 先处理出字符串中 $Alice$ 和 $Bob$ 的下标列表,注意题目中说明的正确检索出 $Alice$ 和 $Bob$ 的条件。
- 考虑到 $K$ 的范围过大,所以用滑动窗口来分别统计 $Alice$ 、$Bob$ 和 $Bob$ 、$Alice$ 这两种不同类别出现的数目。这两个类别求和即为答案。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码
from collections import deque
def en(a):
if ord(a)>=ord('a') and ord(a) <= ord('z'):
return True
if ord(a)>=ord('A') and ord(a) <= ord('Z'):
return True
return False
def check1(i):
if s[i:i+5]=='Alice' and (not en(s[i-1])) and (not en(s[i+5])):
return True
return False
def check2(i):
if s[i:i+3]=='Bob' and (not en(s[i-1])) and (not en(s[i+3])):
return True
return False
if __name__ == '__main__':
k=int(input())
s=list(input().strip())
s.insert(0,'.')
s.append('.')
s="".join(s)
ans=0
notea=[]
noteb=[]
for i in range(len(s)-5):
if check1(i):
notea.append(i)
for i in range(len(s)-3):
if check2(i):
noteb.append(i)
de=deque()
j=0
for i in range(len(notea)):
while j<len(noteb) and noteb[j]<notea[i]:
j+=1
while len(de) and de[0]<notea[i]:
de.popleft()
while j<len(noteb) and noteb[j]-notea[i]-5<=k:
de.append(noteb[j])
j+=1
ans+=len(de)
de=deque()
j=0
for i in range(len(noteb)):
while j<len(notea) and notea[j]<noteb[i]:
j+=1
while len(de) and de[0]<noteb[i]:
de.popleft()
while j<len(notea) and notea[j]-noteb[i]-3<=k:
de.append(notea[j])
j+=1
ans+=len(de)
print(ans)