写在前面

本次给大家带来2026年10月11日拼多多笔试题的4道题，本场机考题目可在咱们平台上在线刷题。

大厂笔试AI Coding练习:CodeFun2000.com/aicoder-gym

第1题-水箱指令对调数

题目内容

实验水箱的容量上限为 ，开机时水位为 。

操作清单上按顺序记有  条指令，第  条记为整数 ：

• ：注入  单位水；
• ：排出  单位水；
• ：只做水位核对，水位不变。

执行指令时，把指令数值累加到当前水位上。称一次完整执行安全，意思是：任意前缀执行完后，水位始终落在闭区间  内（可以贴边，不能越界）。

实验员抄单时一定会把某一处相邻两条指令的次序抄反。对每个下标 （），考虑交换第  条与第  条后，再按新顺序执行全部指令。

请统计有多少个下标 ，使得交换后的执行过程仍然安全。

注意：

1. 必须恰好交换一对相邻指令，原顺序本身不计入；
2. 即使 ，下标  仍是一个合法的抄反位置，交换后若安全则计入；
3. 当  时不存在相邻对，答案为 。

题解

解题思路

采用前缀和与越界计数算法，通过两次遍历解决问题。

设原序列执行完前  条指令后的水位为：

核心结论：交换相邻两条指令，只会改变一个前缀的水位。

交换第  条与第  条指令后：

• 前  条指令不变，水位不变。
• 执行完第  条指令后的水位，由  变为 。
• 执行完第  条及之后指令的水位均不变。

因此，无须重新模拟整个序列。

具体步骤：

1. 第一次遍历，模拟原序列，统计水位越界的前缀数量 。
2. 第二次遍历，枚举每个相邻交换位置，计算原水位  和交换后的水位 。
3. 从  中减去  的越界贡献，得到其他位置的越界数量 。
4. 若  且 ，说明交换后所有前缀都安全，答案加 。

当  时，仍然正常判断并计数；当  时，没有相邻位置，结果自然为 。

复杂度分析

• 时间复杂度：，两次线性遍历指令序列。
• 空间复杂度：，用于存储指令数组；算法额外空间为 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defcount_swaps(m, V, s, d):    water = s    bad = 0# 统计原顺序中越界的前缀数for x in d:        water += xif water < 0or water > V:            bad += 1    water = s    ans = 0# 交换相邻两项时，只有第一项后的水位发生变化for i in range(m - 1):        old = water + d[i]        now = water + d[i + 1]        other_bad = badif old < 0or old > V:            other_bad -= 1if other_bad == 0and0 <= now <= V:            ans += 1        water = oldreturn ansdefmain():    m = int(input())    V = int(input())    s = int(input())    d = list(map(int, input().split()))    print(count_swaps(m, V, s, d))if __name__ == '__main__':    main()

第2题-测温共值最长段

题目内容

机房按天记录服务器机柜温度。第  天的读数是一个闭区间 ，表示真实温度（取整数刻度）可能落在该区间内。共有  天记录，并按日期先后排列。

需要选出一段非空的连续日期，下标记为 。在这段日期中，允许至多把一天的记录当作故障并丢弃，也可以一天都不丢。丢弃后至少还要留下一天记录，并且存在整数 ，落在每一条保留记录的闭区间内。换言之，未丢弃的那些天里，真实温度都有可能取同一个整数 。

所选连续段的跨度定义为 ；被丢弃的那一天仍然计入跨度。请给出合法跨度的最大值。

题解

解题思路

采用滑动窗口 + 优先队列（堆） + 懒删除。

对于当前窗口 ，定义：

• 、：窗口内所有  的最大值和第二大值。
• 、：窗口内所有  的最小值和第二小值。

相同的数值需要重复计算，因为它们可能来自不同日期。

当窗口长度不超过  时，一定合法，因为最多删除一天后仍可保留至少一天。

当窗口长度至少为  时，合法的充要条件为：

原因如下：

如果 ，所有区间本身就有公共交集，无须删除。

否则，最大左端点与最小右端点发生冲突，且它们必然来自不同日期。要消除冲突，只可能：

1. 删除最大左端点所在的记录，此时需要 。
2. 删除最小右端点所在的记录，此时需要 。

因此，只要上述两个条件中有一个成立，窗口就合法。

实现时，用大根堆维护左端点，用小根堆维护右端点。堆中同时保存数值与下标，利用懒删除清理窗口外的元素。暂时弹出堆顶，即可获得第二大值或第二小值，随后将堆顶放回。

不断扩大右端点 。如果当前窗口不合法，就右移左端点 ，直到窗口重新合法，并更新最大长度。

复杂度分析

• 时间复杂度：。每个元素进入两个堆各一次，过期元素最多删除一次；滑动窗口左右端点均最多移动  次，每次堆操作为 。
• 空间复杂度：。两个优先队列最多保存  个元素。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import sysimport heapqdeflongest_span(m, a, b):    max_a, min_b = [], []    left = ans = 0for right in range(m):# 两个堆分别维护左端点最大值、右端点最小值        heapq.heappush(max_a, (-a[right], right))        heapq.heappush(min_b, (b[right], right))while right - left + 1 > 2:# 懒删除：移除窗口左侧的过期堆顶while max_a[0][1] < left:                heapq.heappop(max_a)while min_b[0][1] < left:                heapq.heappop(min_b)# 暂取堆顶，得到左端点第二大值            first_a = heapq.heappop(max_a)while max_a[0][1] < left:                heapq.heappop(max_a)            second_a = -max_a[0][0]            heapq.heappush(max_a, first_a)# 同理得到右端点第二小值            first_b = heapq.heappop(min_b)while min_b[0][1] < left:                heapq.heappop(min_b)            second_b = min_b[0][0]            heapq.heappush(min_b, first_b)# 删除最大左端点或最小右端点之一即可相交if second_a <= min_b[0][0] or -max_a[0][0] <= second_b:break            left += 1        ans = max(ans, right - left + 1)return ansdefmain():    m = int(sys.stdin.readline())    a = list(map(int, sys.stdin.readline().split()))    b = list(map(int, sys.stdin.readline().split()))    print(longest_span(m, a, b))if __name__ == "__main__":    main()

第3题-干线枢纽最小费

题目内容

要在  个站点之间建成一张可互相传输的光纤骨干网（即全部站点连通）。

站点之间已有  条双向预埋管道。建网手段有两种，可混合使用：

1. 启用管道：对已有管道，花费代价  将其启用为光纤干线；启用后两端站点即可互通。
2. 设立枢纽：在站点  设立枢纽，花费为 。所有设立了枢纽的站点，会经由平台专用空中光链路两两互通，因而在骨干网中视为已连通。

骨干网中至少要有一个枢纽；当  时也必须设立。

请计算：让全部站点互相可达所需的最小总花费。

题解

解题思路

采用滑动窗口 + 优先队列（堆） + 懒删除。

对于当前窗口 ，定义：

• 、：窗口内所有  的最大值和第二大值。
• 、：窗口内所有  的最小值和第二小值。

相同的数值需要重复计算，因为它们可能来自不同日期。

当窗口长度不超过  时，一定合法，因为最多删除一天后仍可保留至少一天。

当窗口长度至少为  时，合法的充要条件为：

原因如下：

如果 ，所有区间本身就有公共交集，无须删除。

否则，最大左端点与最小右端点发生冲突，且它们必然来自不同日期。要消除冲突，只可能：

1. 删除最大左端点所在的记录，此时需要 。
2. 删除最小右端点所在的记录，此时需要 。

因此，只要上述两个条件中有一个成立，窗口就合法。

实现时，用大根堆维护左端点，用小根堆维护右端点。堆中同时保存数值与下标，利用懒删除清理窗口外的元素。暂时弹出堆顶，即可获得第二大值或第二小值，随后将堆顶放回。

不断扩大右端点 。如果当前窗口不合法，就右移左端点 ，直到窗口重新合法，并更新最大长度。

复杂度分析

• 时间复杂度：。每个元素进入两个堆各一次，过期元素最多删除一次；滑动窗口左右端点均最多移动  次，每次堆操作为 。
• 空间复杂度：。两个优先队列最多保存  个元素。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import sysimport heapqdeflongest_span(m, a, b):    max_a, min_b = [], []    left = ans = 0for right in range(m):# 两个堆分别维护左端点最大值、右端点最小值        heapq.heappush(max_a, (-a[right], right))        heapq.heappush(min_b, (b[right], right))while right - left + 1 > 2:# 懒删除：移除窗口左侧的过期堆顶while max_a[0][1] < left:                heapq.heappop(max_a)while min_b[0][1] < left:                heapq.heappop(min_b)# 暂取堆顶，得到左端点第二大值            first_a = heapq.heappop(max_a)while max_a[0][1] < left:                heapq.heappop(max_a)            second_a = -max_a[0][0]            heapq.heappush(max_a, first_a)# 同理得到右端点第二小值            first_b = heapq.heappop(min_b)while min_b[0][1] < left:                heapq.heappop(min_b)            second_b = min_b[0][0]            heapq.heappush(min_b, first_b)# 删除最大左端点或最小右端点之一即可相交if second_a <= min_b[0][0] or -max_a[0][0] <= second_b:break            left += 1        ans = max(ans, right - left + 1)return ansdefmain():    m = int(sys.stdin.readline())    a = list(map(int, sys.stdin.readline().split()))    b = list(map(int, sys.stdin.readline().split()))    print(longest_span(m, a, b))if __name__ == "__main__":    main()

第4题-全边巡检最小费用

题目内容

运维员要在一张通信网里完成一次闭环巡检。网中有  个节点（编号  到 ）和  条链路，链路按输入顺序编号为  到 。第  条链路连接节点 ，通行费用为 。保证整张网连通；允许自环与重边。

运维员初始位于节点 ，可反复执行以下两类操作：

1. 实地巡检：沿一条连接当前节点与邻接节点  的链路行走，完成对该链路的巡检并到达 ，花费恰为该链路费用。每条链路至少巡检一次。
2. 调度专线：从当前节点  瞬移到任意其他节点 （）。可自选一条  到  的路径（允许重复经过节点与链路），专线票价等于该路径上编号最大的那条链路的费用。即若路径依次经过编号  的链路，则票价为 。

请计算：从节点  出发，使全部链路都被实地巡检覆盖，最后返回节点  时的最小总花费。

题解

解题思路

使用并查集重构树与奇度点配对。

首先，每条链路实地巡检一次的费用固定为 。重复实地经过一条非自环链路，可以改为沿该链路调度专线，费用不增加；重复经过自环则可以直接省略。因此只需考虑每条链路实地巡检恰好一次。原图连通，要形成从节点  出发并回到节点  的欧拉回路，只需用专线将所有奇度点两两配对。

关键在于专线票价。按编号依次加入链路，设  为加入第  条链路后、包含该链路的连通块。对于  内任意两个不同节点，都能选择一条经过第  条链路、且不经过更大编号链路的路径，所以可以支付  进行传送。

据此按编号建立并查集重构树：原节点为叶子；链路连接两个不同连通块时，新建父节点并记录费用 ；若两端已经连通，则用  更新当前连通块对应树节点的最小费用。由于祖先连通块内的专线也能用于子连通块，按树节点编号从大到小传播最小费用，得到 。任意两点间的最低专线费用，就是它们在重构树中的最近公共祖先对应的  值。

子树越小，可选的专线费用不会越高，因此优先在子树内部配对一定不劣。设  表示子树内奇度点数量的奇偶性。按树节点编号从小到大处理：如果左右子树的  都为 ，就在当前节点配对一次，加上 ；然后令 。

最终答案为实地巡检费用  加上所有配对费用。自环使度数增加 ，不会改变奇偶性。

复杂度分析

时间复杂度：，其中  为反阿克曼函数。并查集处理  条链路，重构树最多有  个节点，正反各遍历一次。

空间复杂度：，用于存储输入链路、并查集和重构树。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import sysdefsolve(p, x, y, c):    parent = list(range(p))    size = [1] * p    root = list(range(p))    left = [0] * (2 * p)    right = [0] * (2 * p)    cost = [10**9 + 1] * (2 * p)    odd = [0] * (2 * p)    k = p    ans = 0deffind(v):while parent[v] != v:            parent[v] = parent[parent[v]]            v = parent[v]return vfor u, v, w in zip(x, y, c):        ans += w        odd[u] ^= 1        odd[v] ^= 1# 自环会翻转两次，奇偶性不变        a, b = find(u), find(v)if a == b:# 当前连通块可以用这条边的费用传送            cost[root[a]] = min(cost[root[a]], w)else:# 按编号合并连通块，建立重构树            left[k], right[k] = root[a], root[b]            cost[k] = wif size[a] < size[b]:                a, b = b, a            parent[b] = a            size[a] += size[b]            root[a] = k            k += 1# 父节点的低票价可以用于子连通块for v in range(k - 1, p - 1, -1):        a, b = left[v], right[v]        cost[a] = min(cost[a], cost[v])        cost[b] = min(cost[b], cost[v])# 两侧都剩一个奇度点时，在当前连通块内配对for v in range(p, k):        a, b = left[v], right[v]if odd[a] and odd[b]:            ans += cost[v]        odd[v] = odd[a] ^ odd[b]return ansdefmain():    read = sys.stdin.buffer.readline    g = int(read())    out = []for _ in range(g):        p, q = map(int, read().split())        x = [int(v) - 1for v in read().split()] if q else []        y = [int(v) - 1for v in read().split()] if q else []        c = list(map(int, read().split())) if q else []        out.append(str(solve(p, x, y, c)))    print(' '.join(out))if __name__ == '__main__':    main()