适用于以下的情境:
① 数组 / 字符串中,有多少个满足情况的连续区间。
② 数组 / 字符串,合并。
【第十三届pythonB组试题:近似gcd】
1. 题目描述
2. 难度:⭐⭐⭐⭐
3. 思考分析:
具体参考:第十三届蓝桥杯国赛 C++ C组 F 题、Python B组 E 题——近似GCD(AC)_蓝桥杯python,bc组的题一样吗?-CSDN博客
① tmp 记录上一个不满足条件的数的位置。
② 设置 right 作为区间到达的最远处;若碰到不满足情况的数字,指针 left=tmp+1,使其始终满足“每个区间内至多一个不满足条件的数字”。
③该区间的长度,即为区间的数目。
import mathn, g = map(int, input().split())
ans = list(map(int, input().split()))res = 0
tmp = -1 #记录上一个不符合条件的数
left, right = 0, 0
for right in range(n):t = math.gcd(g, ans[right])#自始至终只能保证有一个不符合条件的数在区间内if t!=g:left = tmp + 1tmp = rightif right-left+1>=2:res += right - left
print(res)
【第十届JavaB组试题:最长子序列】
1. 题目描述
2. 难度:⭐
3. 思考分析:
分别用 a, b 两个指针指向两个字符串,当满足相等情况时,才接着向后移动。
s = input()
t = input()a=0;b=0
ans = 0
while a<len(s) and b<len(t):if s[a]==t[b]:a += 1b += 1ans += 1else:a +=1
print(ans)
【第十四届C/C++B组试题:合并数列】
1. 题目描述
2. 难度:⭐⭐⭐
3. 思考分析
①利用“双指针”时,不要改变指针指向的数组的内容;而是选择另一个衡量标准——“当前的数组和是否相等”。
②当使用“while循环”时,需格外注意其循环条件:有可能p==n-1,但此时q!=(m-1)且sumA!=sumB。但两个数组的数组和必然是相等的,因此只需要再合并数组余下的数即可。
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))p=0;q=0
sumA=0;sumB=0
ans = 0
while p<n and q<m:if sumA==sumB:sumA += a[p]sumB += b[q]p+=1;q+=1elif sumA<sumB:sumA += a[p]p += 1ans += 1elif sumA>sumB:sumB += b[q]q += 1ans += 1
if p==n and q==m:print(ans)
else:print(ans+(n-p)+(m-q))