ARTICLE · 1059978
拼多多9月22日机考笔试题与解析
拼多多9月22日机考笔试题与解析
写在前面
本次给大家带来2026年9月22日拼多多笔试题的4道题，本场机考题目可在咱们平台上在线刷题。
大厂笔试AI Coding练习:CodeFun2000.com/aicoder-gym
第1题-工位等量连搬
题目内容
装配车间里，今晚要处理的工位排成一行，一共 个。第 个工位待下线的零件个数是 。
夹具每次勾取时，只能框住下标连续的一段 ，并且这段里各个工位的零件个数必须彼此相等，对不齐就不能勾。被勾中的工位只是零件清零，工位仍留在原处，因此左右两段不会贴合。
每个工位上的零件必须整批勾走，不能拆成两次。请给出清空整行所需的最少勾取次数。
题解
解题思路
夹具一次只能框住原序列上一段零件个数完全相同的连续工位。工位本身不撤走，中间清空后左右也不会贴到一起。
每个工位都要被勾到，而且同一工位的零件必须整批勾走，所以每一段被勾中的区间都落在某一个极大等值段内部。 把一个极大等值段拆成多次勾，次数只会更多。因此每一段恰好勾一次是最优的。 左右两段零件个数相同，只要中间还隔着别的个数，就不能并进同一次。答案等于从左到右扫出来的段数。 实现时维护上一个工位的零件个数，当前值不同就把答案加一。只有一个工位时答案是 。
复杂度分析
时间复杂度：。每组询问把该行工位扫一遍。 空间复杂度：。存当前这一行的零件个数。
，。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defcount_runs(xs):# 工位留在原位，不相邻的同值不会贴合，答案就是极大等值段的段数ifnot xs:return0 runs = 1for i in range(1, len(xs)):# 和左边零件个数不同，就必须新开一次勾取if xs[i] != xs[i - 1]: runs += 1return runsdefsolve_cases(cases):# 每组询问单独数段，互不影响return [count_runs(xs) for xs in cases]defmain():# 首行是询问条数，随后每行先是工位数，再跟各工位零件个数 q = int(input()) cases = []for _ in range(q): row = list(map(int, input().split())) m = row[0] cases.append(row[1:1 + m]) ans = solve_cases(cases)# 全部答案写在同一行，空格分隔 print(" ".join(str(x) for x in ans))if __name__ == "__main__": main()第2题-双色条码最长保留
题目内容
质检台送来一条双色墨点条码。每颗墨点要么是浅色，要么是深色：浅色记成字母 ，深色记成字母 。
把一条条码叫作合格条码，意思是它能从左到右切成三段相接的部分，并且：
靠前那一段里，出现过的墨点全都是浅色
正中那一段里，出现过的墨点全都是深色
靠后那一段里，出现过的墨点全都是浅色
三段都允许一颗墨点都没有。
换种说法：浅色只能堆在深色块的两侧，深色自己连成中间那一块。
质检员可以擦掉任意几颗墨点，一颗都不擦也行。擦完以后，留下的墨点还得保持原来从左往右的相对次序。请算出擦完后，合格条码最多能留下几颗墨点。
墨点个数 满足 。
题解
解题思路
留下的墨点必须仍按原顺序排成「浅色段 + 深色段 + 浅色段」，三段都允许为空。同一种颜色在自己那一段里全部留下不会更差，所以只要决定深色段覆盖原条码的哪一段下标。
设条码为 ，长度为 。选定切分点 （）：下标落在 的位置只留 ， 只留 ， 只留 。 用前缀计数 、 表示前 颗里浅色、深色各有多少。这一对切分的长度是，也就是 再加上只跟 有关的部分。 右端点 从 扫到 ，顺手维护 时 的最大值。每个 用这个最大值更新答案。 时深色段为空，全留浅色；整段都划进深色段时，两侧浅色可以为空。
复杂度分析
时间复杂度：。前缀和扫一遍，右端点再扫一遍。 空间复杂度：。保存两个前缀数组。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
deflongest_keep(t, m):# 前缀里浅色 a、深色 b 各有多少颗，下标覆盖 0 到 m cnt_a = [0] * (m + 1) cnt_b = [0] * (m + 1)for i in range(m): cnt_a[i + 1] = cnt_a[i] cnt_b[i + 1] = cnt_b[i]if t[i] == "a": cnt_a[i + 1] += 1else: cnt_b[i + 1] += 1 total_a = cnt_a[m]# best_diff：左端点不超过当前右端点时，左段 a 个数减去左段 b 个数的最大值 best_diff = -10**18 ans = 0for j in range(m + 1): diff = cnt_a[j] - cnt_b[j]if diff > best_diff: best_diff = diff# 右端点定在 j：左段用最优切分，中段把区间里的 b 全部留下，右段把后面的 a 全部留下 cur = best_diff + cnt_b[j] + (total_a - cnt_a[j])if cur > ans: ans = curreturn ansdefmain():# 第一行是墨点数，第二行是条码 m = int(input()) t = input().strip() print(longest_keep(t, m))if __name__ == "__main__": main()第3题-货格最少框边
题目内容
冷链仓被切成边长为 的方格。仓内摆着 件货，每件独占一格，位置用列号、行号标出。
巡检只允许框一次。这个框是边长为 的正方形，里面正好盖住 个完整方格，框中的货会一次读完。框越大越费电。请在读到的货不少于 件的前提下，求出最小的 。
题解
解题思路
方格列号、行号都在 到 之间。边长为 的框就是连续 列、连续 行。 越大越容易凑够 件，因此可以二分最小的 。
把每件货记到 的方格表上。货的位置互不相同。 做二维前缀和。查询任意连续列、连续行里的件数是 。 检查边长 时，枚举框的左上角。闭区间列 、行 的件数不少于 ，这个边长就可行。 若选中若干件货，列号最小最大是 ，行号最小最大是 ，盖住它们的最小边长是 。所以答案落在 到 之间，而且最优框可以贴着这些货，不会伸到编号范围外面。 只需要 件时，答案直接是 。
复杂度分析
时间复杂度：，其中 。前缀和先花 ，二分大约 轮，每一轮最坏扫描 个左上角。 空间复杂度：。方格表和前缀和都是这个量级。
货的件数最多 ，判定过程只跟方格边长上限 有关。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
V = 1000defmin_side(k, cols, rows):# 只要求框到 1 件时，任意一格的边长都是 1if k <= 1:return1 width = V + 1# 列、行都从 1 编号，把每件货记到对应方格 grid = [0] * (width * width)for c, r in zip(cols, rows): grid[c * width + r] = 1# ps[c][r] 表示列 1..c、行 1..r 这一块里的件数 ps = [0] * (width * width)for c in range(1, V + 1): running = 0 cur = c * width prev = (c - 1) * widthfor r in range(1, V + 1): running += grid[cur + r] ps[cur + r] = ps[prev + r] + runningdefenough(side):# 枚举左上角，统计边长为 side 的闭区间里有多少件货 span = side - 1 last = V - spanfor c in range(1, last + 1): hi = (c + span) * width lo = (c - 1) * widthfor r in range(1, last + 1): r2 = r + span total = ps[hi + r2] - ps[hi + r - 1] - ps[lo + r2] + ps[lo + r - 1]if total >= k:returnTruereturnFalse# 边长越大越容易凑够 k 件，二分最小可行边长 low, high = 1, Vwhile low < high: mid = (low + high) // 2if enough(mid): high = midelse: low = mid + 1return lowdefmain(): k = int(input()) p = int(input()) cols = list(map(int, input().split())) rows = list(map(int, input().split())) print(min_side(k, cols, rows))if __name__ == "__main__": main()第4题-开合区间校验
题目内容
一条报文写成字符串 ，一共 个字符。每个字符要么是开符 [，要么是合符 ]。
调度一共做 次动作，只有下面两类。
第一类给出两端 ，把第 个到第 个字符全部换成对面：[ 换成 ]，] 换成 [。
第二类给出两端 ，问当前这一段是否配平。
配平的含义：从左往右扫描这一段，遇到 [ 就让计数加 ，遇到 ] 就让计数减 。扫描途中计数始终不能小于 ，扫到末尾时计数必须回到 。
例如 []、[[]]、[][] 都配平；][、[[]、][][ 都不配平。
题解
解题思路
一段报文配平，等价于两件事同时成立：从左端点起的前缀和始终不小于 ，并且整段的和等于 。开符贡献 ，合符贡献 。
建一棵线段树。每个节点记下这段的和、最小前缀和、最大前缀和。 左右两段合并时，和直接相加。最小前缀要么停在左边，要么是左边的和再加上右边的最小前缀。最大前缀同样处理。 把一整段开合对调，每个数都变号。于是区间和取反，原来的最大前缀变成新的最小前缀（再加一个负号），原来的最小前缀变成新的最大前缀。节点上挂一个懒标记，标记再遇到一次就抵消。 修改或询问之前，先把路径上的懒标记下传，避免父亲的对调和孩子的数值打架。 询问时取出覆盖 的若干段，按从左到右拼出和与最小前缀。和为 且最小前缀不小于 就输出 ，否则输出 。对调操作不输出。
复杂度分析
时间复杂度：。每次对调或询问只碰到 个节点。 空间复杂度：。线段树按报文长度的常数倍开。
和 最大都是 。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defsolve(w, ops):# 开符记 +1，合符记 -1。配平 <=> 区间和为 0 且最小前缀和 >= 0 n = len(w) base = 1while base < n: base <<= 1 height = base.bit_length() - 1# 叶子放在 base 起的位置，凑不满的叶子保持 0，询问范围不会落到那里 sm = [0] * (base << 1) mn = [0] * (base << 1) mx = [0] * (base << 1) lz = [0] * (base << 1)for i, ch in enumerate(w): v = 1if ch == "["else-1 leaf = base + i sm[leaf] = mn[leaf] = mx[leaf] = vfor p in range(base - 1, 0, -1): left = p << 1 right = left | 1 ls = sm[left] sm[p] = ls + sm[right] mn[p] = mn[left] if mn[left] < ls + mn[right] else ls + mn[right] mx[p] = mx[left] if mx[left] > ls + mx[right] else ls + mx[right] ans = []for op, a, b in ops:if op == 1:# 对调 [a, b]：先把路径上的懒标记推下去，再覆盖这一段，最后向上重算# 1 起编号的闭区间 [a, b] 对应叶子 [base+a-1, base+b) left = base + a - 1 right = base + b idx = leftfor shift in range(height, 0, -1): p = idx >> shiftif lz[p]: c = p << 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 c |= 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 lz[p] = 0 idx = right - 1for shift in range(height, 0, -1): p = idx >> shiftif lz[p]: c = p << 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 c |= 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 lz[p] = 0 begin_l = left begin_r = rightwhile left < right:if left & 1: sm[left] = -sm[left] mn[left], mx[left] = -mx[left], -mn[left] lz[left] ^= 1 left += 1if right & 1: right -= 1 sm[right] = -sm[right] mn[right], mx[right] = -mx[right], -mn[right] lz[right] ^= 1 left >>= 1 right >>= 1# 父亲若仍挂着对调标记，用孩子重算后再把标记作用回去 idx = begin_lwhile idx > 1: idx >>= 1 leftc = idx << 1 rightc = leftc | 1 ls = sm[leftc] sm[idx] = ls + sm[rightc] mn[idx] = mn[leftc] if mn[leftc] < ls + mn[rightc] else ls + mn[rightc] mx[idx] = mx[leftc] if mx[leftc] > ls + mx[rightc] else ls + mx[rightc]if lz[idx]: sm[idx] = -sm[idx] mn[idx], mx[idx] = -mx[idx], -mn[idx] idx = begin_r - 1while idx > 1: idx >>= 1 leftc = idx << 1 rightc = leftc | 1 ls = sm[leftc] sm[idx] = ls + sm[rightc] mn[idx] = mn[leftc] if mn[leftc] < ls + mn[rightc] else ls + mn[rightc] mx[idx] = mx[leftc] if mx[leftc] > ls + mx[rightc] else ls + mx[rightc]if lz[idx]: sm[idx] = -sm[idx] mn[idx], mx[idx] = -mx[idx], -mn[idx]else:# 询问 [a, b] 的区间和与最小前缀和# 1 起编号的闭区间 [a, b] 对应叶子 [base+a-1, base+b) left = base + a - 1 right = base + b idx = leftfor shift in range(height, 0, -1): p = idx >> shiftif lz[p]: c = p << 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 c |= 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 lz[p] = 0 idx = right - 1for shift in range(height, 0, -1): p = idx >> shiftif lz[p]: c = p << 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 c |= 1 sm[c] = -sm[c] mn[c], mx[c] = -mx[c], -mn[c] lz[c] ^= 1 lz[p] = 0 left_parts = [] right_parts = []while left < right:if left & 1: left_parts.append(left) left += 1if right & 1: right -= 1 right_parts.append(right) left >>= 1 right >>= 1 total = 0 best = Nonefor p in left_parts: cand = total + mn[p]if best isNoneor cand < best: best = cand total += sm[p]for j in range(len(right_parts) - 1, -1, -1): p = right_parts[j] cand = total + mn[p]if best isNoneor cand < best: best = cand total += sm[p] ans.append(1if total == 0and best >= 0else0)return ansdefmain(): m = int(input()) t = int(input()) w = input().strip() ops = []for _ in range(t): op, a, b = map(int, input().split()) ops.append((op, a, b))for bit in solve(w, ops): print(bit)if __name__ == "__main__": main()