大厂真题 / 米哈游
米哈游 2026-8-16 笔试真题 - 运维开发（平台向）
本场考试概述
考试时间：2026 年 8 月 16 日
考试岗位：运维开发（平台向）· 2 卷
难度评级：中等偏下
考点分析：
- 第 1 题：前缀和、值域约束剪枝（中等）
- 第 2 题：Bash、awk 文本处理（简单）
建议策略：
- 第 1 题不要直接枚举所有子数组。由 $\lvert a_i\rvert\le 100$ 可以推出合法子数组长度不超过 $100$，据此将枚举量降到 $O(100n)$。
- 第 2 题重点是按输入阶段读取数据，并用关联数组完成版本过滤、平台去重和原顺序输出。
第 1 题：子数组和等于长度平方
题目描述
给定一个长度为 $n$ 的整数数组 $a$。定义任意非空子数组 $[l,r]$ 的长度为
\[L=r-l+1,\]其元素和为 $\sum_{i=l}^{r}a_i$。请统计满足
\[\sum_{i=l}^{r}a_i=L^2\]的子数组个数。
子数组是从原数组中连续选择一段元素得到的新数组。
输入描述
每个测试文件包含多组测试数据。
第一行输入整数 $T$，满足 $1\le T\le 10^5$。
每组测试数据包含两行：
- 第一行输入整数 $n$，满足 $1\le n\le 10^5$；
- 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $\lvert a_i\rvert\le100$。
所有测试数据的 $n$ 之和不超过 $2\times10^5$。
输出描述
对于每组测试数据，输出一个整数，表示满足条件的子数组个数。
样例 1
输入
1
5
1 4 0 3 1
输出
4
解释
长度为 $1$ 时，数组中的两个 1 分别贡献一个答案。长度为 $2$ 时，子数组 [4,0] 与 [3,1] 的和均为 $4$，再贡献两个答案，合计为 $4$。
样例 2
输入
2
3
-1 2 3
4
1 2 2 4
输出
0
2
思路分析
预处理前缀和 prefix，其中 prefix[i] 表示前 $i$ 个元素之和。长度为 $L$、右端点为 right - 1 的子数组和可以在 $O(1)$ 时间内写成：
如果直接枚举所有长度，复杂度仍为 $O(n^2)$。关键是利用元素值域：长度为 $L$ 的子数组最多只能取得 $100L$ 的和，而题目要求其和为 $L^2$，所以必要条件为
\[L^2\le100L.\]由于 $L>0$，可得 $L\le100$。因此只需枚举 $1$ 到 $\min(n,100)$ 的长度，再扫描所有对应子数组。
数组允许出现负数，但不影响上述上界：$100L$ 仍然是区间和的最大可能值。
正确性证明
引理 1：长度大于 $100$ 的子数组不可能满足题目条件。
证明：任意元素均不大于 $100$，因此长度为 $L$ 的子数组和不大于 $100L$。当 $L>100$ 时，$L^2>100L$，子数组和不可能达到 $L^2$。引理得证。
引理 2：算法能够正确判断每个长度不超过 $100$ 的子数组是否满足条件。
证明：前缀和之差 prefix[right] - prefix[right - L] 恰好等于该长度为 $L$ 的连续区间内所有元素之和。算法将其与 $L^2$ 比较，因此判断结果与题目定义一致。引理得证。
定理：算法输出的计数恰好等于所有满足条件的子数组数量。
证明：由引理 1，所有可能满足条件的子数组长度都在算法枚举范围内；算法对每种合法长度的所有连续区间各检查一次，没有遗漏或重复。由引理 2，每次判断均正确，所以最终计数恰好是答案。定理得证。
ACM Python 代码
import sys
def count_good_subarrays(values):
n = len(values)
prefix = [0] * (n + 1)
for i, value in enumerate(values, 1):
prefix[i] = prefix[i - 1] + value
answer = 0
for length in range(1, min(n, 100) + 1):
target = length * length
for right in range(length, n + 1):
if prefix[right] - prefix[right - length] == target:
answer += 1
return answer
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
test_cases = data[0]
cursor = 1
output = []
for _ in range(test_cases):
n = data[cursor]
cursor += 1
values = data[cursor:cursor + n]
cursor += n
output.append(str(count_good_subarrays(values)))
sys.stdout.write("\n".join(output))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度为 $O(100n)$，对全部测试数据合计最多进行约 $2\times10^7$ 次区间和判断。
空间复杂度为 $O(n)$，用于保存输入数组和前缀和。
易错点
- 不能仍按 $O(n^2)$ 枚举所有左右端点；长度上界 $100$ 是本题的核心。
- 多组数据的 $n$ 之和有限制，应一次读取输入并顺序解析。
- 区间和与答案计数都建议使用 64 位整数；Python 整数会自动扩容。
- 前缀和下标要统一：长度为 $L$、右边界为
right的区间使用prefix[right] - prefix[right - L]。
第 2 题：资源包缺失清单
题目描述
游戏活动上线前，运营平台会为每个活动场景准备一组资源包，并分别在 android、ios、pc 三个平台生成资源就绪记录。请根据资源计划和平台检查日志，输出仍缺少就绪记录的资源包清单。
对每条资源计划，只有在要求版本下同时存在三个平台的 READY 记录，才认为该资源包发布完整。
统计规则如下：
- 同一资源包、同一版本、同一平台可以出现多条记录，只要至少存在一条
READY即可； FAIL不能替代READY；- 非要求版本的记录不计入；
- 未出现在资源计划中的日志忽略。
输入描述
第一行包含两个整数 $R,C$，满足 $1\le R\le10000$、$0\le C\le30000$。
随后 $R$ 行为资源计划，每行包含三个空白分隔字段：
resource_id scene required_version
再随后 $C$ 行为平台检查日志，每行包含四个空白分隔字段：
resource_id version platform status
其中 platform 只会是 android、ios、pc，status 只会是 READY 或 FAIL。
各字段长度为 $1$ 到 $50$，只包含大小写字母、数字、点号、下划线和短横线。resource_id 在资源计划中互不重复，输入格式合法且不存在空行或多余空格。
输出描述
按资源计划给出的先后顺序，逐行输出每个发布不完整的 resource_id。若所有资源包均发布完整，输出 none。
样例 1
输入
3 7
pkg_a scene1 v1.0
pkg_b scene1 v1.0
pkg_c scene2 v2.0
pkg_a v1.0 android READY
pkg_a v1.0 ios READY
pkg_a v1.0 pc READY
pkg_b v1.0 android READY
pkg_b v1.0 ios FAIL
pkg_b v1.0 pc READY
pkg_c v1.5 android READY
输出
pkg_b
pkg_c
样例 2
输入
2 7
pkg_x sceneA build-1
pkg_y sceneA build-1
pkg_x build-1 android FAIL
pkg_x build-1 android READY
pkg_x build-1 ios READY
pkg_x build-1 pc READY
pkg_y build-1 android READY
pkg_y build-1 ios READY
pkg_y build-1 pc READY
输出
none
思路分析
使用一个 awk 程序单遍处理输入：
- 首行读取资源计划数量
R。 - 接下来的
R行记录每个资源包的要求版本，并用order数组保留输入顺序。 - 对日志行，仅接受“资源包在计划内、版本匹配、状态为 READY”的记录。
- 使用
seen[resource_id, platform]对同平台的重复READY去重，再累计每个资源包已就绪的平台数。 - 在
END块中按计划顺序输出就绪平台数小于3的资源包。
awk 的关联数组本身不保证按插入顺序遍历，因此必须额外保存 order[i]。
正确性证明
引理 1：计数数组 ready_count[id] 等于资源包 id 在要求版本下拥有 READY 记录的平台种类数。
证明：日志处理条件排除了计划外资源、错误版本和 FAIL 记录；seen[id, platform] 又保证同一平台至多计数一次。因此每次增量对应一个不同且有效的平台，所有有效平台也都会被处理。引理得证。
引理 2：脚本输出且仅输出发布不完整的资源包。
证明：平台集合固定为 android、ios、pc。由引理 1，ready_count[id] = 3 当且仅当三个平台均已有有效 READY 记录。因此 ready_count[id] < 3 当且仅当资源包发布不完整。引理得证。
定理：脚本按资源计划顺序输出全部发布不完整的资源包；若不存在则输出 none。
证明：order 完整保存计划中的资源包顺序，END 块依次检查每一项，并由引理 2 准确决定是否输出。若没有任何输出项，标志变量保持为假，脚本输出 none。定理得证。
题解代码
import sys
def solve():
data = sys.stdin.buffer.read().splitlines()
if not data:
return
R, C = map(int, data[0].split())
order, required, ready = [], {}, set()
pos = 1
for _ in range(R):
resource_id, _scene, version = data[pos].decode().split()
pos += 1
order.append(resource_id)
required[resource_id] = version
for _ in range(C):
resource_id, version, platform, status = data[pos].decode().split()
pos += 1
if resource_id in required and version == required[resource_id] and status == "READY":
ready.add((resource_id, platform))
missing = [resource_id for resource_id in order
if sum((resource_id, platform) in ready for platform in ("android", "ios", "pc")) < 3]
sys.stdout.write("\n".join(missing or ["none"]))
if __name__ == "__main__":
solve()
Bash 代码
#!/usr/bin/env bash
awk '
NR == 1 {
R = $1
next
}
NR <= R + 1 {
position = NR - 1
order[position] = $1
required_version[$1] = $3
next
}
$4 == "READY" && ($1 in required_version) && $2 == required_version[$1] {
key = $1 SUBSEP $3
if (!(key in seen)) {
seen[key] = 1
ready_count[$1]++
}
}
END {
missing = 0
for (i = 1; i <= R; i++) {
id = order[i]
if (ready_count[id] < 3) {
print id
missing = 1
}
}
if (!missing) {
print "none"
}
}
'
复杂度分析
时间复杂度为 $O(R+C)$，每条计划和日志只处理一次。
空间复杂度为 $O(R+K)$，其中 $K$ 是通过过滤的不同“资源包—平台”组合数，且 $K\le3R$。
易错点
FAIL后出现同平台READY时，该平台仍应视为就绪。- 同一平台的多条
READY只能计数一次。 - 必须先判断
($1 in required_version)，再访问要求版本，避免把计划外资源误纳入统计。 - 不能直接遍历
awk关联数组输出，否则无法保证资源计划中的原始顺序。 - 版本必须完全匹配，其他版本即使三个平台都
READY也无效。
知识点总结
- 值域约束经常可以推导出枚举维度的常数上界。看到 $\lvert a_i\rvert\le100$ 和目标值 $L^2$ 时，应立即比较区间最大和 $100L$ 与目标值。
- 前缀和负责将定长区间求和降到 $O(1)$，长度剪枝负责将总复杂度从平方级降到线性级常数倍。
awk适合处理按行组织的结构化文本：普通数组保存输出顺序，关联数组完成映射、集合和去重。- 运维开发类笔试不仅考算法，也会直接考 Shell、日志过滤和文本处理能力。