大厂真题 / 荣耀
荣耀 2026-05-06 笔试真题 - 通用岗
本场考试概述
考试时间:2026年5月6日 考试岗位:通用 难度评级:中等偏难
考点分析:
- 第一题:模拟(难度简单)
- 第二题:数值线性代数 — Gram矩阵 + Jacobi特征值分解(难度困难)
- 第三题:模拟 + 多关键字排序(难度中等)
建议策略:
- 第一题是经典模拟,细心实现队列操作即可,是拿满分的基础
- 第二题涉及矩阵伪逆和SVD,关键洞察是”伪逆奇异值 = 原矩阵奇异值的倒数”,用Gram矩阵 + Jacobi迭代即可
- 第三题多关键字排序要注意优先级顺序,贪心选满足间隔条件的天数
第 1 题:老鹰捉小鸡
题目描述
老鹰捉小鸡游戏模拟。游戏开始时有 $m$ 只小鸡组成队列(每只小鸡有唯一编号,但未必有序)。游戏共进行 $n$ 轮,每轮老鹰指定攻击当前队列中第 $a$ 个小鸡,鸡妈妈指定保护第 $b$ 个小鸡(均从 1 开始计数)。
规则:
- 若 $a$ 超过当前队列长度,本轮攻击无效
- 若 $b$ 超过当前队列长度,本轮防守无效
- 若 $a = b$ 且两者均有效,则攻击失败
- 否则,第 $a$ 个小鸡退出队列,后面小鸡向前补位
小鸡个数 $\leq 1$ 时游戏立即失败结束;$n$ 轮后仍有 $> 1$ 只小鸡则游戏胜利。
游戏失败输出 Fail! 和剩余小鸡编号;游戏胜利输出 Success! 和剩余编号(按递增排列)。
样例
输入
4 3
40 30 20 10
2 1 2 1 1 1
输出
Success! 10 40
思路分析
第一步:理清模拟逻辑
这道题没有算法难点,考的是仔细实现规则。用一个列表维护当前小鸡队列,逐轮读入攻击和保护位置。
第二步:每轮判断三种情况
- 攻击位置 $a$ 超出队列长度 — 跳过
- $a$ 未越界且保护位置 $b$ 也未越界且 $a = b$ — 攻击失败
- 其他情况 — 攻击命中,删除第 $a$ 个小鸡
第三步:终止条件
每次成功删除后立即检查:队列长度 $\leq 1$ 则游戏失败,不再进行后续轮次。
以样例为例:初始队列 [40, 30, 20, 10]
- 第 1 轮:$a=2, b=1$,不同,删第 2 个(30),队列变
[40, 20, 10] - 第 2 轮:$a=2, b=1$,不同,删第 2 个(20),队列变
[40, 10] - 第 3 轮:$a=1, b=1$,相同,攻击失败
最终剩余 2 只,胜利。排序输出 10 40。
题解代码
import sys
input = sys.stdin.readline
def main():
m, n = map(int, input().split())
chicks = list(map(int, input().split()))
raw = list(map(int, input().split()))
for r in range(n):
atk, prt = raw[2 * r], raw[2 * r + 1]
sz = len(chicks)
if atk > sz:
continue
if prt <= sz and atk == prt:
continue
del chicks[atk - 1]
if len(chicks) <= 1:
break
if len(chicks) <= 1:
print(f"Fail! {chicks[0]}")
else:
chicks.sort()
print("Success! " + " ".join(map(str, chicks)))
main()
复杂度分析
时间复杂度:$O(mn)$,$n$ 轮操作,每次删除最坏移动 $O(m)$ 个元素 空间复杂度:$O(m + n)$
第 2 题:矩阵处理
题目描述
给定一个矩阵 $A$,依次完成三步操作:
- 将矩阵 $A$ 中每个元素 $x$ 替换为”大于等于 $x$ 的最小 2 的幂的指数”,得到矩阵 $B$
- 求矩阵 $B$ 的伪逆,得到矩阵 $C$
- 求矩阵 $C$ 的全部非零奇异值,输出最大的 5 个(保留两位小数)
输入格式:矩阵用方括号包裹,行用分号隔开,列用空格隔开。
样例
输入
[42 42 96 29 5 89 91 94 13 5 24 67 74 93 35 32;73 56 54 14 54 63 58 70 28 11 50 27 78 92 95 90;1 15 70 2 67 76 1 7 59 23 62 7 91 40 59 58;31 20 32 68 52 35 62 76 97 72 83 38 94 97 88 19;15 81 69 22 95 27 33 76 57 56 16 63 2 18 85 79;10 97 84 27 59 90 53 93 2 2 2 22 24 13 91 62;19 32 2 50 91 43 89 72 81 8 8 76 62 14 46 6;35 70 76 6 14 97 36 13 24 97 49 7 95 51 55 43;40 88 99 58 14 67 91 2 81 57 61 27 96 3 80 68;54 90 75 15 81 63 63 3 39 21 57 81 56 95 29 92;42 9 29 59 40 12 2 3 87 26 32 20 92 83 50 1;69 4 79 70 17 95 93 25 75 75 99 64 65 2 60 98;21 17 11 11 93 45 70 87 56 20 58 53 40 18 2 38;88 88 45 42 35 58 100 54 14 59 39 93 49 34 60 98;3 10 91 70 76 41 18 56 6 98 56 27 61 14 44 61;68 43 30 42 73 24 14 85 13 85 75 7 55 81 81 83]
输出
4.49 1.52 0.86 0.66 0.37
思路分析
第一步:理解元素变换规则
题目说”大于等于 $x$ 的最小 2 的幂”。根据样例反推,存的是指数 $k$ 而非 $2^k$。例如 $x = 42$ 时,$2^5 = 32 < 42$,$2^6 = 64 \geq 42$,所以替换为 $k = 6$。当 $x \leq 1$ 时 $k = 0$。实现上用 math.ceil(math.log2(x)) 计算。
第二步:关键数学洞察 — 不需要真的算伪逆
伪逆矩阵 $C = B^+$ 的非零奇异值恰好等于原矩阵 $B$ 非零奇异值的倒数。因此只需求出 $B$ 的奇异值再取倒数即可,完全不需要显式计算伪逆。
第三步:用 Gram 矩阵将 SVD 转化为特征值问题
矩阵 $B$ 的奇异值平方 = $B^T B$ 的特征值。若 $B$ 是 $n \times m$ 的矩阵,$B^T B$ 是 $m \times m$ 的对称矩阵。对称矩阵的特征值可以用 Jacobi 旋转法 求解:
- 反复找矩阵中绝对值最大的非对角元素 $g_{ij}$
- 构造一次 Givens 旋转将 $g_{ij}$ 消成 0
- 迭代直到所有非对角元素足够小
最终矩阵变成对角阵,对角线上就是特征值。
第四步:组装答案
对角线正值开平方得到 $B$ 的奇异值,取倒数得到伪逆的奇异值,降序排列输出前 5 个。
题解代码
import sys
import math
def main():
text = sys.stdin.read()
inner = text[text.index('[') + 1 : text.rindex(']')]
grid = []
for seg in inner.split(';'):
seg = seg.strip()
if seg:
grid.append([float(w) for w in seg.split()])
rows, cols = len(grid), len(grid[0])
# 元素变换:ceil(log2(x))
for i in range(rows):
for j in range(cols):
v = grid[i][j]
if v <= 1:
grid[i][j] = 0.0
else:
grid[i][j] = math.ceil(math.log2(v))
# 构造 Gram 矩阵(取维度较小的那边以加速)
dim = min(rows, cols)
g = [[0.0] * dim for _ in range(dim)]
if rows >= cols:
for r in range(rows):
for ci in range(cols):
for cj in range(ci, cols):
g[ci][cj] += grid[r][ci] * grid[r][cj]
for ci in range(cols):
for cj in range(ci):
g[ci][cj] = g[cj][ci]
else:
for ri in range(rows):
for rj in range(ri, rows):
acc = 0.0
for c in range(cols):
acc += grid[ri][c] * grid[rj][c]
g[ri][rj] = g[rj][ri] = acc
# Jacobi 旋转迭代求特征值
tol = 1e-12
for _ in range(200 * dim * dim):
mx, mi, mj = 0.0, 0, 0
for i in range(dim):
for j in range(i + 1, dim):
if abs(g[i][j]) > mx:
mx = abs(g[i][j])
mi, mj = i, j
if mx < tol:
break
ii, jj, ij = g[mi][mi], g[mj][mj], g[mi][mj]
theta = (jj - ii) / (2.0 * ij)
sgn = 1.0 if theta >= 0 else -1.0
t = sgn / (abs(theta) + math.sqrt(1.0 + theta * theta))
cos = 1.0 / math.sqrt(1.0 + t * t)
sin = t * cos
for k in range(dim):
if k == mi or k == mj:
continue
old_ki = g[k][mi]
old_kj = g[k][mj]
g[k][mi] = g[mi][k] = cos * old_ki - sin * old_kj
g[k][mj] = g[mj][k] = sin * old_ki + cos * old_kj
g[mi][mi] = cos * cos * ii - 2.0 * sin * cos * ij + sin * sin * jj
g[mj][mj] = sin * sin * ii + 2.0 * sin * cos * ij + cos * cos * jj
g[mi][mj] = g[mj][mi] = 0.0
# 伪逆的奇异值 = 1 / 原奇异值
inv_sv = []
for i in range(dim):
ev = g[i][i]
if ev > 1e-8:
inv_sv.append(1.0 / math.sqrt(ev))
inv_sv.sort(reverse=True)
print(" ".join(f"{x:.2f}" for x in inv_sv[:5]))
main()
复杂度分析
时间复杂度:$O(p^3)$,其中 $p = \min(n, m)$,Jacobi 迭代主导 空间复杂度:$O(p^2)$,存储 Gram 矩阵
第 3 题:项目组成员每日步数分析
题目描述
统计项目组成员上班时间步行情况并排序输出。一个月上班时间按 22 天计算。
评价规则(按优先级从高到低,命中即停):
- 有 4 天及以上每天步数 $> 30000$,且这些天两两间隔 $> 4$ 天 →
excellent - 有 15 天以上每天步数 $> 10000$ →
excellent - 有 15 天以上每天步数在 $(5000, 10000)$ 区间 →
good - 有 18 天以上每天步数 $< 5000$ →
bad
排序优先级:规则1 > 规则2 > 规则3 > 规则4;同一规则内按总步数降序;总步数相同按输入顺序。
输出格式:名字:评价 总步数。某评价类型为空则输出对应的 null 信息。
样例
输入
Gsy:35000 0 0 0 0 36000 0 0 0 0 0 40000 0 0 0 0 32000
Wj:12000 12000 12000 12000 12000 12000 12000 0 12000 12000 12000 12000 0 12000 12000 12000 12000 12000 12000
Jww:2000
Zzc:6000 6000 6000 6000 0 6000 6000 6000 0 0 6000 6000 6000 6000 6000 6000 6000 6000 6000 6000 6000 6000 6000
Dbw:3000
输出
Gsy:excellent 143000
Wj:excellent 204000
Zzc:good 120000
Dbw:bad 3000
Jww:bad 2000
思路分析
第一步:数据预处理
按冒号拆出姓名和每日步数。不足 22 天的末尾补 0,超过 22 天的只取前 22 天做评价判断。但总步数按所有输入天数的累加(不截断)。
第二步:四条规则按顺序判断
规则 1 是最有趣的 — 要从 22 天中选出 $\geq 4$ 天步数 $> 30000$ 且任意两天间隔 $> 4$。这用贪心解决:从第 1 天扫到第 22 天,碰到步数满足条件且离上一次选中的天间距 $> 4$,就贪心选上。越早选给后面留的空间越大,不会错过任何可行方案。
以样例 Gsy 为例:步数 [35000, 0, 0, 0, 0, 36000, 0, 0, 0, 0, 0, 40000, 0, 0, 0, 0, 32000, ...]
- 第 0 天:35000 > 30000,距离上次(-100)足够,选中,计数=1
- 第 5 天:36000 > 30000,距第 0 天间隔 5 > 4,选中,计数=2
- 第 11 天:40000 > 30000,距第 5 天间隔 6 > 4,选中,计数=3
- 第 16 天:32000 > 30000,距第 11 天间隔 5 > 4,选中,计数=4 ✓
规则 2/3/4 直接统计满足条件的天数即可。
第三步:排序输出
排序键:(规则优先级, -总步数, 输入顺序)。排完后分 excellent/good/bad 三个桶依次输出,空桶输出 null 提示。
题解代码
import sys
WORK_DAYS = 22
def check_spaced_high(daily):
"""贪心:能否在22天中选出>=4天步数>30000且相邻选中天间隔>4"""
picked, prev = 0, -100
for d in range(WORK_DAYS):
if daily[d] > 30000 and d - prev > 4:
picked += 1
prev = d
if picked >= 4:
return True
return False
def classify(daily):
"""按4条规则依次判断,命中即返回"""
if check_spaced_high(daily):
return 1, "excellent"
above_10k = sum(1 for x in daily if x > 10000)
if above_10k > 15:
return 2, "excellent"
mid_range = sum(1 for x in daily if 5000 < x < 10000)
if mid_range > 15:
return 3, "good"
below_5k = sum(1 for x in daily if x < 5000)
if below_5k > 18:
return 4, "bad"
return 0, None
def main():
lines = sys.stdin.read().splitlines()
records = []
any_valid = False
for idx, raw in enumerate(lines):
raw = raw.strip()
if not raw:
continue
any_valid = True
colon = raw.index(':')
name = raw[:colon]
nums_str = raw[colon + 1:].strip()
nums = [int(x) for x in nums_str.split()] if nums_str else []
total = sum(nums)
daily = (nums + [0] * WORK_DAYS)[:WORK_DAYS]
pri, tag = classify(daily)
if tag is not None:
records.append((pri, -total, idx, name, tag, total))
if not any_valid:
print("There is no data.")
return
records.sort()
groups = {"excellent": [], "good": [], "bad": []}
for pri, _, _, name, tag, total in records:
groups[tag].append(f"{name}:{tag} {total}")
for cat in ("excellent", "good", "bad"):
if groups[cat]:
for line in groups[cat]:
print(line)
else:
print(f"{cat} is null")
main()
复杂度分析
时间复杂度:$O(n \log n)$,$n$ 为成员数,排序主导 空间复杂度:$O(n)$
小结
- 第一题是经典队列模拟,核心是仔细处理越界判断和终止条件,属于送分题
- 第二题是本场最难的题,考察数值线性代数知识。关键洞察”伪逆奇异值 = 原奇异值的倒数”避免了显式计算伪逆,Jacobi 旋转法是对称矩阵求特征值的经典迭代算法
- 第三题的排序逻辑不难,但规则 1 的”间隔约束选天数”需要贪心思想。多关键字排序利用 Python 的元组比较一次 sort 即可完成