写在前面

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

第一题：从左扫到右，相邻同色就断开重计，维护当前段长度和历史最长即可。

第二题：货一到就 I 入栈，栈顶正好是下一个该出的号就立刻 O；扫完后若全部出完则动作串唯一，否则输出 N。

第三题：状态 (站点, 剩余油) 做堆优化最短路：本站补 1 单位油，或走耗油不超过当前油量的公路；到不了输出 -1。

第四题：区间到整点的匹配：若某段窗里“完全落在这段内的人数”超过窗数，答案全 0；若正好装满，这段里的窗都不能留空。按右端点扫描，用线段树维护霍尔差额即可。

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

第1题-最长异色连续灯带

题目内容

灯带车间今晚要量一段展台灯带的可用长度。值班员必须找出最长的一段连续色号，使得相邻两格颜色都不同，并把这个长度写入工艺单。

灯带用小写字母串  表示，每个字母是一种色号。一段非空连续子串如果任意两个相邻字符都不同，就称为一段异色带。请输出  中最长异色带的长度。

串长满足 100000，且  只含小写字母。

输入描述

一行一个字符串 （100000），只含小写英文字母。

输出描述

输出一个整数，即最长异色带的长度。

样例1

输入

xyzzyx

输出

3

说明

xyz 与 zyx 都是长度为 3 的异色带。中间 zz 相邻同色，不能整段算进去。

样例2

输入

bbba

输出

2

说明

前面连续的 b 只能各算长度 1，ba 相邻不同，最长为 2。

样例3

输入

abcab

输出

5

说明

整串相邻都不相同，最长就是 。

题解

解题思路

异色带就是相邻色号都不相同的连续段。从左扫到右，同色就断开重计即可。

1. 用  记当前这段异色带长度， 记历史最长。
2. 若 ，当前段可以延长一格；否则从这一格重新开始，长度为 。
3. 单字符一定合法，所以答案至少是 。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

代码实现

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

defsolve(w):# 扫一遍，相邻同色就断开，统计当前段长度  best = 1  cur = 1for i in range(1, len(w)):if w[i] != w[i - 1]:      cur += 1if cur > best:        best = curelse:      cur = 1return bestw = input().strip()print(solve(w))

第2题-唯一入栈出库序列

题目内容

中转仓今晚只有一条暂存滑轨，滑轨按栈工作：后进的货先出。值班员必须按货号从小到大出库，并记下唯一的入轨、出库动作；若做不到就在日志里写失败标记。

共有  件货按到达顺序经过主道，第  件的货号是 。 是  的一个排列。出库顺序必须恰好是 。

每件货到达时，值班员必须立刻做下面两种动作之一：

• I：把它推进暂存栈；
• 若规则允许，之后用 O 弹出栈顶出库。

任意时刻只要栈顶正好是下一个该出的货号，就必须立刻 O 出库。可以证明：能成功时，动作序列是唯一的。

请判断能否按号出完。能则输出由 I 和 O 组成的动作串（恰好  个 I 和  个 O）；不能则输出 N。

货件数满足 200000。

输入描述

第一行一个正整数 （200000），表示货件数。

第二行  个正整数 ，保证是  的排列。

输出描述

若存在合法方案，输出一行由 I 和 O 组成的字符串；否则输出一行一个字符 N。

样例1

输入

43 1 2 4

输出

IIOIOOIO

说明

3、1 入栈后弹出 1，再让 2 入栈并连续弹出 2、3，最后 4 入栈再出库。

样例2

输入

32 3 1

输出

N

说明

2、3 入栈后，1 再入再出，栈顶变成 3，下一个该出的是 2，卡死。

样例3

输入

11

输出

IO

说明

只有一件货，入栈后立刻出库。

题解

解题思路

暂存滑轨是栈。货号必须按  出库，能成功时动作唯一：货一到就入栈，栈顶正好是下一个该出的号就立刻出。

1. 用栈模拟，并记下下一个该出的货号 ，从  开始。
2. 扫到一件货就执行 I 入栈；然后只要栈顶等于 ，就执行 O 并把  加一。
3. 全部到达后若 ，说明出完了，输出动作串；否则栈里还堵着更大的号，输出 N。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

代码实现

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

defsolve(k, v):# 贪心：货一到就入栈，栈顶刚好是下一个该出的号就立刻出  st = []  ops = []  need = 1for x in v:    st.append(x)    ops.append("I")while st and st[-1] == need:      st.pop()      ops.append("O")      need += 1if need == k + 1:return"".join(ops)return"N"k = int(input())v = list(map(int, input().split()))print(solve(k, v))

第3题-巡检车最短补油用时

题目内容

巡检队要把一辆巡检车从 1 号站开到  号站。值班员必须按油箱容量规划补油，使总用时最短，并把这个时间写入调度单；到不了就记失败。

共有  个站点、 条双向公路。每条公路用四个整数  描述：连接  与 ，耗油 ，耗时  分钟。出发时油箱是满的，容量为 ，油量不能超过 。在站点  每补 1 单位油要花  分钟。

请计算从站点  到站点  的最短用时；无法到达则输出 -1。

站点数满足 ，公路数满足 ，油箱容量满足 。各站补油耗时满足 ，公路耗油满足 ，公路耗时满足 ，站点编号在  之间。

输入描述

第一行三个整数 、、（，，），表示站点数、公路数和油箱容量。

第二行  个整数 （），表示各站每补 1 单位油的分钟数。

接下来  行，每行四个整数 、、、（，，），表示一条双向公路。

输出描述

输出一个整数，即从站点  到站点  的最短用时；无法到达则输出 -1。

样例1

输入

3 2 44 1 91 2 2 32 3 2 4

输出

7

说明

出发油量是 4。 耗油 2、耗时 3，到达时还剩 2，正好够走 （耗时 4），总用时 7，中途不用补油。

样例2

输入

2 1 32 81 2 5 4

输出

-1

说明

唯一一条路要耗油 5，油箱容量只有 3，到不了。

样例3

输入

2 1 35 11 2 2 8

输出

8

说明

出发油量够直接开过去，用时就是公路上的 8 分钟。

题解

解题思路

油箱容量不大，把「在哪个站、还剩多少油」当成状态，按时间做最短路。

1. 状态  表示在站点 、剩余油量 。出发是 ，时间为 。
2. 两种转移：在本站补 1 单位油，到 ，加时 ；或者走一条耗油不超过  的公路，到对面站点并扣油，加时为路耗时。
3. 用堆优化的最短路更新这些状态。到达  号站时，所有剩余油量里的最小时间就是答案；一次都到不了则是 -1。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

代码实现

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

import heapqdefsolve(k, q, r, edges):# 状态 (城市, 剩余油量)，边权是时间  g = [[] for _ in range(k + 1)]for a, b, c, t in edges:    g[a].append((b, c, t))    g[b].append((a, c, t))  inf = 10 ** 18  dist = [[inf] * (q + 1) for _ in range(k + 1)]# 出发时油箱是满的  dist[1][q] = 0  h = [(0, 1, q)]while h:    tm, u, f = heapq.heappop(h)if tm != dist[u][f]:continue# 在当前城加 1 单位油if f < q:      nf = f + 1      ntm = tm + r[u - 1]if ntm < dist[u][nf]:        dist[u][nf] = ntm        heapq.heappush(h, (ntm, u, nf))# 有油就走相邻路for v, c, t in g[u]:if f >= c:        nf = f - c        ntm = tm + tif ntm < dist[v][nf]:          dist[v][nf] = ntm          heapq.heappush(h, (ntm, v, nf))  ans = min(dist[k])if ans >= inf:return-1return ansfirst = list(map(int, input().split()))k, e, q = firstr = list(map(int, input().split()))edges = []for _ in range(e):  a, b, c, t = map(int, input().split())  edges.append((a, b, c, t))print(solve(k, q, r, edges))

第4题-哪个查阅窗能留空

题目内容

档案室夜班要把当天的调档请求排进一排查阅窗。值班员必须先给自己留出一个空窗去核总账，再判断剩下的窗够不够分给所有调档员，并把每个窗能不能留空写进值班日志。

今晚共有  名调档员，查阅窗编号为 ，一共  个窗。第  名调档员只接受闭区间  里的整数编号窗。每名调档员必须恰好分到一个窗，同一个窗最多分给一名调档员。

对每个窗 ，请独立判断：如果窗  完全不分配、专门留给值班员，是否仍然能把全部  名调档员安排到各自能接受、且互不冲突的窗上。

请按窗号从小到大输出判断结果。判断不同的  时，可以采用完全不同的分配方案。

调档员人数满足 ，且 。

输入描述

第一行一个整数 （），表示调档员人数。

接下来  行，第  行两个整数 、（），表示第  名调档员能接受的窗号闭区间。

输出描述

输出一个长度为  的 01 字符串。第  个字符为 1，当且仅当存在一种合法安排，使全部调档员都分到窗、且窗  不分配给任何人；否则为 0。

样例1

输入

11 2

输出

11

说明

只有一名调档员，两个窗都能接受。留空窗 1 时分到 2，留空窗 2 时分到 1，两种都可行。

样例2

输入

31 42 23 3

输出

1001

说明

• 留空窗 1：三人可分别分到 4、2、3。
• 留空窗 2：第二人只接受窗 2，无法安排。
• 留空窗 3：第三人只接受窗 3，无法安排。
• 留空窗 4：三人可分别分到 1、2、3。

样例3

输入

31 21 22 2

输出

0000

说明

三人都只能挤在窗 1、2 里，这两个窗本身就装不下三个人。无论留空哪一个窗，都无法安排，因此四个位置都是 0。

题解

解题思路

这是区间到整点的匹配。一共  个窗、  个人，留空窗  后还剩  个窗。区间匹配满足霍尔定理，当且仅当每个连续窗段  里，“区间完全落在这段内的人数”不超过这段的窗数。

1. 记  为满足  且  的人数。若存在 ，这段窗本身就装不下这些人，无论留空哪个窗都失败，答案是全 0。
2. 若 ，这段窗被这批人正好占满，其中任何一个窗都不能留空。所有这样的装满段取并，对应位置输出 0，其余输出 1。
3. 按右端点  从左到右加入区间，用线段树维护 （左端点小于  且已加入的人数）。一次扫描即可找出是否溢出、以及每个  对应的最左装满左端点。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

代码实现

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

defsolve(k, segs):# 共有 k+1 个窗。f(L,R) = 完全落在 [L,R] 内的人数# 若某段 f > 长度，整体无解；若 f == 长度，这段里每个窗都不能留空  m = k + 1  by_r = [[] for _ in range(m + 2)]for p, q in segs:    by_r[q].append(p)# 线段树维护 h(L) = L - (左端点 < L 且右端点已加入的人数)  size = 1while size < m + 2:    size *= 2  mx = [0] * (2 * size)  mn = [0] * (2 * size)  lz = [0] * (2 * size)for i in range(1, m + 2):    mx[size + i] = i    mn[size + i] = ifor i in range(size - 1, 0, -1):    mx[i] = mx[2 * i] if mx[2 * i] > mx[2 * i + 1] else mx[2 * i + 1]    mn[i] = mn[2 * i] if mn[2 * i] < mn[2 * i + 1] else mn[2 * i + 1]defapp(i, v):# 整段加上延迟标记    mx[i] += v    mn[i] += v    lz[i] += vdefpush(i):if lz[i] != 0:      app(2 * i, lz[i])      app(2 * i + 1, lz[i])      lz[i] = 0defpull(i):    mx[i] = mx[2 * i] if mx[2 * i] > mx[2 * i + 1] else mx[2 * i + 1]    mn[i] = mn[2 * i] if mn[2 * i] < mn[2 * i + 1] else mn[2 * i + 1]defadd(l, r, v, i=1, L=0, R=None):# 区间 [l,r] 上的 h 全部加 vif R isNone:      R = size - 1if r < L or R < l:returnif l <= L and R <= r:      app(i, v)return    push(i)    mid = (L + R) // 2    add(l, r, v, 2 * i, L, mid)    add(l, r, v, 2 * i + 1, mid + 1, R)    pull(i)defqmax(l, r, i=1, L=0, R=None):if R isNone:      R = size - 1if r < L or R < l:return-10 ** 18if l <= L and R <= r:return mx[i]    push(i)    mid = (L + R) // 2    a = qmax(l, r, 2 * i, L, mid)    b = qmax(l, r, 2 * i + 1, mid + 1, R)return a if a > b else bdefleft_eq(l, r, val, i=1, L=0, R=None):# [l,r] 里最左的、h 恰好等于 val 的位置if R isNone:      R = size - 1if r < L or R < l or mx[i] < val or mn[i] > val:returnNoneif L == R:return L if mx[i] == val elseNone    push(i)    mid = (L + R) // 2    a = left_eq(l, r, val, 2 * i, L, mid)if a isnotNone:return areturn left_eq(l, r, val, 2 * i + 1, mid + 1, R)  total = 0  overflow = False  diff = [0] * (m + 3)for R in range(1, m + 1):# 右端点等于 R 的人加入；相同左端点合并成一次区间加if by_r[R]:      cnt = {}for p in by_r[R]:        cnt[p] = cnt.get(p, 0) + 1for p, c in cnt.items():        total += cif p + 1 <= m:          add(p + 1, m, -c)elif overflow:continueelse:continueif overflow:continue# g(L) = f(L,R) + L - (R+1) = h(L) + total - (R+1)    gmx = qmax(1, R) + total - (R + 1)if gmx > 0:# 某段人比窗多，无论留哪个空窗都失败      overflow = Trueelif gmx == 0:# 存在装满段 [L,R]，这段里的窗都不能留空      target = (R + 1) - total      L = left_eq(1, R, target)if L isnotNone:        diff[L] += 1        diff[R + 1] -= 1if overflow:return"0" * m  ans = []  s = 0for t in range(1, m + 1):    s += diff[t]# 差分数 > 0 说明落在某个装满段里    ans.append("0"if s > 0else"1")return"".join(ans)k = int(input())segs = []for _ in range(k):  p, q = map(int, input().split())  segs.append((p, q))print(solve(k, segs))