笔试时间：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版本，此时球球并不能通过击败其他球球壮大自己，而是获得得分，每一个球球都有一