写在前面

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

第一题：先数出每种任务出现几次，用出现最多的那种当骨架、按冷却间隔把它们拉开，其余任务去填空档；空档填不满就按骨架长度算，填得满答案就是任务总数。

第二题：路网是树，每条路几乎都要走一个来回才能覆盖全图，但最后停在离起点最远的那个点，所以用两倍边权和减去从起点出发的最远距离。

第三题：先算出每个点在随机先序里的期望位置，得到不改任何权值时的期望分；再枚举改哪一个点——没兄弟就只换它自己的权，有兄弟则两棵子树的期望位置各平移一截，取这些方案里最大的。

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

第1题-同类单据冷却排期

题目内容

档案室新上了一台高速扫描工位，当天要处理一批纸质单据。工位只认 26 种单据类型，分别用大写字母 A 到 Z 标记。排班员拿到一份长度为  的类型序列，每个位置对应一张单据，同一类型可以出现多次。工位每个单位时间可以处理恰好一张单据，也可以空转一个单位时间不处理任何单据。

设备手册规定：同一种类型相邻两次处理之间，必须隔开长度为  的冷却窗口。也就是说，若某张类型为  的单据在时刻  处理完毕，则下一张同类型单据最早只能排在时刻 。冷却窗口内可以安排其他类型，也可以空转。

单据的处理次序可以任意重排，不必保持输入顺序。求处理完所有单据所需的最短时间。

输入描述

第一行一个整数 （），表示单据张数。

第二行一个长度为  的字符串，仅由大写字母 A 到 Z 组成，第  个字符表示第  张单据的类型。

第三行一个整数 （），表示同类单据之间的冷却长度。

输出描述

输出一个整数，表示处理完全部单据的最短时间。

样例1

输入

1Z5

输出

1

说明

只有一张类型 Z 的单据。不存在「下一次同类」，冷却不起作用，最短时间为 1。

样例2

输入

6CCCDDD3

输出

10

说明

C 与 D 各出现 3 次，冷却长度为 3。先把出现最多次的类型按冷却拉开：

C _ _ _ C _ _ _ C

空位用 D 填入后得到

C D _ _ C D _ _ C D

长度为 10。无法更短：两个最多种类都要各处理 3 次，最后一轮会并排放下 C 和 D。

样例3

输入

5EEEEE0

输出

5

说明

冷却长度为 0，同类可以紧挨着处理，最短时间等于单据张数 5。

数据范围

• 类型字符串只含大写字母 A–Z，长度为 
• 所有输入均为整数或上述字符

题解

解题思路

把出现次数最多的类型当作骨架，用冷却长度把它们拉开，其余类型去填空档。

1. 统计每种大写字母的出现次数，记最大次数为 ，达到  的种类数为 。
2. 先排  个「最高频」单据，相邻两次之间至少空出  个位置，形成  段，每段长度为 ，最后再并排放下  个并列最高频类型。骨架长度为 。
3. 若其它单据填不满这些空档，答案就是骨架长度；否则没有空转，答案等于总张数 。
4. 因此最短时间为 。

复杂度分析

• 时间复杂度：。
• 空间复杂度：（只开 26 个计数器）。

代码实现

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

defsolve(n, s, m):# 只会出现 A-Z，用长度为 26 的数组计数  cnt = [0] * 26for ch in s:    cnt[ord(ch) - 65] += 1# mx：出现最多的次数；kinds：有多少种都达到这个次数  mx = max(cnt)  kinds = 0for c in cnt:if c == mx:      kinds += 1# 最高频类型先占位：每两个之间空出 m 格，最后一轮放下 kinds 个并列最高频  frame = (mx - 1) * (m + 1) + kinds# 其它单据若能填满空档，总时间不能短于总张数if frame > n:return framereturn nn = int(input())s = input().strip()m = int(input())print(solve(n, s, m))

第2题-哨所巡护最短路程

题目内容

林场巡护队要把辖区内全部哨所走一遍。辖区里一共有  个哨所，编号为  到 ，队部设在  号哨所。哨所之间由  条小路连成一棵树：任意两个哨所都能互相到达，并且没有回路。每条小路有一个非负长度。

巡护从队部出发，必须到达每一个哨所至少一次；全部走完后不必返回队部。沿小路可以来回走。求完成这次巡护所需的最短总路程。

形式化地：给定一棵  个结点的无向树，边权为非负整数。从结点  出发，找一条（可重复走边）的途径，使得每个结点至少出现一次，最小化途径上边权之和。

输入描述

第一行一个整数 （），表示哨所个数。

接下来  行，每行三个整数 （，），表示  号与  号哨所之间有一条长度为  的小路。

输入保证这些小路构成一棵树。

输出描述

输出一个整数，表示最短巡护路程。

样例1

输入

41 2 11 3 23 4 3

输出

7

说明

边权之和为 6。从队部出发到最远哨所  的距离是 5。每条小路除了通往最远哨所的那条链外都要走一个来回，因此最短路程为 。一条走法是 。

样例2

输入

21 2 10

输出

10

说明

只有一条小路。走到  号哨所即可结束，不必返回，路程为 10。

样例3

输入

61 2 52 3 51 4 14 5 14 6 100

输出

123

说明

边权之和为 112，从  出发最远到达 ，距离 101。最短路程为 。

数据范围

• 共  条边，构成一棵树
• 所有输入均为整数

题解

解题思路

路网是树。从队部出发要覆盖全部结点、最后不必返回，每条边至少走一次，但通往「从  出发最远的那个结点」的那条链不用折返。

1. 把边权和记为 。若每条边都走一个来回，总路程是 ，这对应「走遍后再回到 」。
2. 现在允许停在任意结点，最优是停在距  最远的结点，少走一段长度为  的返程，其中  是从  出发的最大距离。
3. 因此答案为 。
4. 从  做一次树遍历即可同时得到  与 。边权可达 ，点数可达 ，要用  位整数。

复杂度分析

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

代码实现

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

defsolve(n, edges):# 只有一个点时无处可走if n == 1:return0# 建无向树，同时累加全部边权  g = [[] for _ in range(n + 1)]  total = 0for u, v, w in edges:    g[u].append((v, w))    g[v].append((u, w))    total += w# 从 1 号队部遍历，算出到每个哨所的距离  dist = [-1] * (n + 1)  dist[1] = 0  stack = [1]while stack:    u = stack.pop()for v, w in g[u]:if dist[v] < 0:        dist[v] = dist[u] + w        stack.append(v)# 除通往最远哨所的链外，每条边都要走一个来回  farthest = 0for i in range(1, n + 1):if dist[i] > farthest:      farthest = dist[i]return2 * total - farthestn = int(input())edges = []for _ in range(n - 1):  u, v, w = map(int, input().split())  edges.append((u, v, w))print(solve(n, edges))

第3题-双叉滑槽期望评分

题目内容

分拣中心把货位连成一棵有  个结点的二叉树，根结点编号为 0，每个结点至多两个孩子。第  个货位上放着货量 。巡检员按深度优先顺序走完整棵树：走到结点  时先记录 ，再进入其子树。若  恰有两个孩子  与 ，则先走进  的概率为

先走进  的概率为 ；若只有一个孩子，则必定走进该孩子。

记  为结点  被记录的顺序（从 1 开始）。整趟巡检的评分为

调度台可以把至多一个货位的货量改成目标值 ，也可以不改。求改完后评分期望的最大值。

输入描述

第一行一个整数 （），表示结点数。

第二行  个整数，第  个数是结点  的父亲 （$p_i<i$）。数据保证这是一棵二叉树。当 $m="1$" 时这一行为空。<="" p="">

第三行  个整数 （），表示各货位货量。

第四行一个整数 （），表示可改成的目标货量。

输出描述

输出一个实数，表示最大期望评分。绝对误差或相对误差不超过 0.0001 即视为正确。

样例1

输入

30 02 3 410

输出

40.5714

说明

根 0 的两个孩子是 1 和 2。把结点 0 的货量改成 10 时，遍历概率不变，期望评分为 40.5714，优于改其他点或不改。

样例2

输入

208 13

输出

19.0000

说明

链上只有一个孩子，改权值不影响顺序。不改时期望为 17；把结点 0 改成 3 反而变差，把结点 1 改成 3 得到 19。

样例3

输入

40 1 21 2 3 45

输出

36.0000

说明

这是一条链。越早被记录的点系数越大，把根的货量改成 5 最优，期望为 36。

数据范围

• 父亲满足 $p_i
• 所有输入均为整数

题解

解题思路

评分是 ，所以先算出每个点的期望 DFS 序，再枚举「改哪一个点」。

1. 根的序恒为 。若  只有一个孩子 ，则 。若有两个孩子 ，先走  的概率是 ，于是 ， 对称。
2. 不改任何点时，期望评分  可  算出。
3. 把  的货量改成 ：自身贡献变成 。仅当  有兄弟  时，改  才会改写  与  两棵子树内部所有点的期望序，变化量分别是常数 ，对评分的影响也是  可算。
4. 根或独子改权值不改变任何概率。枚举每个  取最大，并与  比较。

复杂度分析

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

代码实现

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

defsolve(n, fa, w, W):# 建二叉树：每个点最多两个孩子  ch = [[] for _ in range(n)]for i in range(1, n):    ch[fa[i - 1]].append(i)  sz = [1] * n  sumw = [0.0] * n  edfn = [0.0] * n# 保证父亲编号更小，倒序即自底向上for u in range(n - 1, -1, -1):    sw = float(w[u])    s = 1for v in ch[u]:      s += sz[v]      sw += sumw[v]    sz[u] = s    sumw[u] = sw# 根的序为 1，再往下推期望序  edfn[0] = 1.0  stack = [0]while stack:    u = stack.pop()    kids = ch[u]if len(kids) == 0:continueif len(kids) == 1:      v = kids[0]      edfn[v] = edfn[u] + 1.0      stack.append(v)continue    a, b = kids[0], kids[1]    wa, wb = float(w[a]), float(w[b])    s = wa + wb    edfn[a] = edfn[u] + 1.0 + (wb / s) * sz[b]    edfn[b] = edfn[u] + 1.0 + (wa / s) * sz[a]    stack.append(a)    stack.append(b)  base = 0.0for i in range(n):    base += w[i] * (n + 1.0 - edfn[i])  best = base# 枚举改一个点；不改已包含在 basefor x in range(n):if w[x] == W:continue    extra = (W - w[x]) * (n + 1.0 - edfn[x])    p = fa[x - 1] if x > 0else-1    sib = -1if p >= 0and len(ch[p]) == 2:      a, b = ch[p][0], ch[p][1]      sib = b if a == x else aif sib >= 0:      wx, ws = float(w[x]), float(w[sib])      old_den = wx + ws      new_den = W + ws      d_x = (ws / new_den - ws / old_den) * sz[sib]      d_s = (W / new_den - wx / old_den) * sz[x]      extra -= d_x * (sumw[x] - w[x] + W)      extra -= d_s * sumw[sib]if base + extra > best:      best = base + extrareturn bestn = int(input())fa = list(map(int, input().split()))w = list(map(int, input().split()))W = int(input())print("%.4f" % solve(n, fa, w, W))