2023 微众银行笔试题 0423
笔试时间：2023年4月23日 春招
第一题
题目：区间计数
给出两个长度均为n的数组A={a1,a2,...,an}，B={b1,b2,...,bn}。你需要求出其有多少个区间[L,R]满足数组A中下标在[L,R]中的元素之和在[La,Ra]之中，且数组B中下标在[L,R]中的元素之和在[Lb,Rb]中。
输入描述
第一行有一个正整数N(1≤N≤100000)，代表两个数组的长度。
第二行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。
第三行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。
第四行有4个整数La,Ra,Lb,Rb，范围在0到1018之间，代表题目描述中的参数。
输出描述
输出一个整数，代表所求的答案。
样例输入
4
1 4 2 3
2 4 1 1
3 7 4 6
样例输出
3
参考题解
前缀和 + 哈希表模拟。假设数组A、B的前缀和数组分别是preA, preB，遍历数组A，B的前缀和数组，只需要找到 区间满足[La,Ra]和[Lb,Rb]即可，这个过程可以使用二分来实现。
Python：
N = int(input())
A = [int(c) for c in input().strip().split(" ")]
B = [int(c) for c in input().strip().split(" ")]
La, Ra, Lb, Rb = map(int, input().strip().split(" "))
preA, preB = [0 for i in range(N + 1)],[0 for i in range(N + 1)]
for i in range(1, N + 1):
preA[i] = preA[i-1] + A[i-1]
preB[i] = preB[i-1] + B[i-1]
cnt = 0
'''找到第一个大于'''
def bcs1(nums, l, r, target):
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return r
'''找到小于等于target的最大值'''
def bcs2(nums, l, r , target):
while l < r:
mid = (l + r + 1) // 2
if nums[mid] <= target: l = mid
else: r = mid - 1
return r
for i in range(N + 1):
'''pre[i] - Ra <= x <= pre[i] - La'''
l, r = 0, i
l1, r1 = bcs1(preA,l, r, preA[i] - Ra), bcs2(preA, l, r, preA[i]-La)
l2, r2 = bcs1(preB, l, r, preB[i] - Rb), bcs2(preB, l, r, preB[i]-Lb)
l3, r3 = max(l1, l2), min(r1,r2)
if La <= preA[i] - preA[l3]<= Ra and La <= preA[i] - preA[r3] <= Ra and Lb <= preB[i] - preB[l3] <= Rb and Lb <= preB[i]-preB[r3]<=Rb:
cnt += r3-l3 + 1
print(cnt)
第二题
题目：吞吞大作战
吞吞大作战是球球大作战的x.0版本，此时球球并不能通过击败其他球球壮大自己，而是获得得分，每一个球球都有一
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2023 秋招笔试题汇总解析 文章被收录于专栏
2023秋招各大笔试题汇总，c++，java，python多种语言分析，解答。
