写在前面

本次给大家带来2026年10月31日中国电信笔试题的3道题，本场机考题目可在咱们平台上在线刷题。

第1题-编号记录变更

题目内容

每个编号初始都没有对应记录，未记录的数值可视为 。按给定顺序处理下列指令：

• PUT key value：把编号 key 的数值设为 value；编号尚无记录时，先建立记录。
• INCREASE key delta：使编号 key 的数值增加 delta；若其当前未登记，则新建一条初始值为  的记录后再增加。
• REMOVE key：当编号 key 有记录时将其删除；否则此次操作无法完成。

每次成功完成 PUT、INCREASE 或 REMOVE 均计为一次成功变更。全部指令处理完毕后，请依次给出成功变更总数、未能完成的 REMOVE 指令数，以及最终仍保留、数值不为  且该编号累计成功变更次数恰为  的编号个数。

各编号的累计成功变更次数分别记录。对某编号成功执行 PUT、INCREASE 或将其记录成功移除，都会使该计数增加 。移除记录时不清除累计计数；之后同一编号再次创建记录，计数从原值接着累加。未成功执行的指令不改变累计计数。

输入描述

首行给出整数 ，表示待处理指令的总数。 再接下来  行，每行描述一条指令，格式为以下三种之一：

• PUT key value
• INCREASE key delta
• REMOVE key

其中 key 为编号，value 与 delta 均为整数。

输出描述

输出一行三个整数，分别表示成功变更次数、失败的 REMOVE 指令数、符合条件的最终编号数量。

• ；
• ；
• 。

任意时刻记录中的数值及输出答案均可用有符号  位整数表示。

样例1

输入：

8PUT 8 4REMOVE 8PUT 8 0INCREASE 9 6REMOVE 9REMOVE 9PUT 11 -2REMOVE 12

输出：

6 2 1

说明

编号 8 成功设置、移除、再次设置，最终数值为  且累计次数为 ；编号 9 创建后又被移除，之后再次移除失败；编号 11 只成功设置一次，最终仍保留且数值为 ；编号 12 从未存在，移除操作失败。因此最终符合条件的编号只有 11。

题解

解题思路

1. 使用哈希表保存当前存在的编号及其数值，使用另一张哈希表保存每个编号累计成功修改的次数。
2. PUT 和 INCREASE 都会创建或修改记录，并令对应编号的累计次数加 。
3. REMOVE 在编号存在时删除当前记录并令累计次数加 ；编号不存在时只增加失败次数。
4. 所有指令处理完后，遍历当前记录。若某编号的数值不为  且累计次数为 ，答案加 。

复杂度分析

每条指令的期望处理时间为 ，总时间复杂度为 ，空间复杂度为 。

代码实现

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

defsolve(ops):# val 保存当前仍存在的记录，cnt 保存每个编号的历史成功操作次数。    val = {}    cnt = {}    ok = bad = 0for op in ops:        t = op[0]        x = int(op[1])        z = int(op[2]) if len(op) == 3else0if t == 'PUT':            val[x] = z            cnt[x] = cnt.get(x, 0) + 1            ok += 1elif t == 'INCREASE':# get 的默认值为 0，同时处理编号首次出现的情况。            val[x] = val.get(x, 0) + z            cnt[x] = cnt.get(x, 0) + 1            ok += 1elif x in val:# 删除当前记录，但不能删除 cnt，否则重新创建时历史次数会丢失。del val[x]            cnt[x] = cnt.get(x, 0) + 1            ok += 1else:# 只有删除不存在的编号才会产生失败次数。            bad += 1# 只统计最终存在、数值非零且历史成功次数恰好为 1 的编号。    ans = sum(1for x, v in val.items() if v != 0and cnt[x] == 1)return ok, bad, ansdefmain():    m = int(input())    ops = [input().split() for _ in range(m)]    print(*solve(ops))if __name__ == '__main__':    main()

第2题-字符串合法切点

题目内容

给出一个由 A、B、C 三种字符构成的字符串 t，其长度记为 m。需要确定两个整数位置 u、v，并满足 1 ≤ u < v < m，以此将 t 切分为 t[1..u]、t[u+1..v]、t[v+1..m] 三个非空且连续的部分。

当每一部分所含的 A 数量都相同，同时每一部分所含的 B 数量也都一致时，称位置对 (u,v) 符合要求；各部分中的 C 数量无需相等。

请在所有符合要求的位置对中，选出字典序最小的 (u,v)。字典序的判定规则是先看位置对第一项，若相等再比较第二项；若不存在符合要求的位置对，则输出 -1 -1。

输入描述

输入一行字符串 t，其中只会出现大写字符 A、B、C。

输出描述

输出两个整数 u、v，对应字典序最小的合法切分位置；无解时输出 -1 -1。

数据范围

3 ≤ m ≤ 200000。

样例1

输入：

ABCCAB

输出：

2 4

说明：切分后得到 AB、CC、AB。三个部分的 A 数均为 ，B 数也均为 。首个切点最小时，第二切点取 4，因此得到字典序最小解 (2,4)。

题解

解题思路

1. 设整个字符串中 A、B 的数量分别为 ca、cb。若任意一种字符的总数不能被  整除，则三段不可能拥有相同数量，直接输出 -1 -1。
2. 三段合法时，第一段的前缀计数必须为 ，前两段的前缀计数必须为 。
3. 从左到右扫描字符串，找到最早满足第一组计数且位置不超过  的切点 ；随后继续扫描，找到最早满足第二组计数且位置至少为 、不超过  的切点 。这两个位置就是字典序最小的合法方案。
4. 扫描过程中维护前缀中 A、B 的数量即可，字符 C 不影响判断。

复杂度分析

时间复杂度为 ，空间复杂度为 。

代码实现

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

defsolve(s):    n = len(s)    ta = s.count('A')    tb = s.count('B')# 总数不是 3 的倍数时，不可能平均分到三段。if ta % 3 != 0or tb % 3 != 0:return-1, -1    a = b = 0    p = -1# 找最早的第一切点，使前缀恰好含有总数的三分之一。for i in range(n - 2):if s[i] == 'A':            a += 1elif s[i] == 'B':            b += 1if a == ta // 3and b == tb // 3:            p = i + 1breakif p == -1:return-1, -1# 从第一段之后继续扫描，找最早满足前两段总计数的第二切点。for i in range(p, n - 1):if s[i] == 'A':            a += 1elif s[i] == 'B':            b += 1if a == 2 * ta // 3and b == 2 * tb // 3:return p, i + 1return-1, -1defmain():    s = input().strip()    p, q = solve(s)    print(p, q)if __name__ == '__main__':    main()

第3题-树层统计查询

题目内容

现在有一棵含  个顶点的无根树，规定顶点  为根。某顶点的深度等于它到根顶点的路径所经过的边数，故根的深度为 。

你需要先给出全树的最大深度、深度等于最大深度的顶点个数，以及叶顶点数目。在无向树里，仅连接一条边的顶点称作叶顶点；若 ，唯一的根同样按叶顶点计算。

接着处理  条询问。每条询问提供一个深度 ，请返回深度正好为  的顶点数量与这些顶点编号的总和。若树中没有对应深度的顶点，打印 。

输入格式

第一行输入一个整数 ，代表树中的顶点数。

后续共有  行，第  行给出整数 ，说明顶点  和  之间直接相邻。

接下来一行是整数 ，表示询问条数。

随后  行各给出一个整数 ，表示本次要统计的深度。

输出格式

首行依次写出最大深度、深度等于最大深度的顶点数和叶顶点总数。

对于每一个询问，依照输入先后各输出一行：深度为  的顶点数以及顶点编号和；不存在该深度时输出 。

• 输入边保证恰好组成一棵无向树。

样例1

输入：

81 21 42 32 54 64 77 8601235100

输出：

3 1 41 12 64 211 80 00 0

样例说明

顶点  的深度为 ；顶点  深度为 ；顶点  深度为 ；顶点  深度为 。故最大深度为 ，其中只有一个顶点。叶顶点是 。当查询深度  时，返回的编号和是 。

题解

解题思路

1. 将无向边存入邻接表，并记录每个顶点的无向度数。除只有一个顶点的情况外，度数为  的顶点就是叶顶点。
2. 从根顶点  开始进行广度优先搜索。搜索到顶点时，它被首次访问的距离就是层号。
3. 对每一个层号 ，维护两个统计值：该层顶点数 cnt[h]，以及该层所有顶点编号之和 sum[h]。
4. 搜索结束后，最深层号即为数组最后一个下标；对于每个查询，若  在统计数组范围内直接输出，否则输出 。

复杂度分析

构建图和广度优先搜索共访问每个顶点、每条边一次，时间复杂度为 ，空间复杂度为 。

代码实现

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

from collections import dequedefsolve(n, edges, qs):    g = [[] for _ in range(n + 1)]    deg = [0] * (n + 1)for u, v in edges:        g[u].append(v)        g[v].append(u)        deg[u] += 1        deg[v] += 1    dep = [-1] * (n + 1)    dep[1] = 0    cnt = []    sm = []    que = deque([1])# BFS 中首次访问到的层号就是根到该点的距离。while que:        u = que.popleft()        d = dep[u]if d == len(cnt):            cnt.append(0)            sm.append(0)        cnt[d] += 1        sm[d] += ufor v in g[u]:if dep[v] == -1:                dep[v] = d + 1                que.append(v)    leaf = 1if n == 1else sum(x == 1for x in deg[1:])    out = [f"{len(cnt) - 1}{cnt[-1]}{leaf}"]for h in qs:if0 <= h < len(cnt):            out.append(f"{cnt[h]}{sm[h]}")else:            out.append("0 0")return outdefmain():    n = int(input())    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]    q = int(input())    qs = [int(input()) for _ in range(q)]    print("\n".join(solve(n, edges, qs)))if __name__ == '__main__':    main()

手机端刷题:塔子哥刷题宝