夜雨聆风写在前面
本次给大家带来2026年8月8日OPPO笔试题的2道题，本场机考题目可在咱们平台上在线刷题。
第一题：先记录排列中每个数字所在的位置，再按 的顺序比较相邻数字的位置大小，统计向左和向右的次数即可；
第二题：先用训练集均值补全缺失值并标准化，再用训练集训练 ，以样本的重建平方误差作为异常分数，并用训练误差的 分位数作为阈值判断测试样本是否异常。
塔子哥的配套刷题网站:codefun2000.com
第1题-序号巡检轨迹
题目内容
一条线性巡检带上依次设置了 个检测点，每个检测点被分配了一个唯一的巡检序号。巡检设备需要严格按照序号从小到大的次序依次访问这些检测点，并记录移动方向。
给定一个长度为 的排列 ，其中 的每个整数都恰好出现一次。
设备最开始位于满足 的下标 处。之后共进行 次移动，每次按照下面的规则前往下一个检测点：
设当前所在位置的下标为 ； 找到唯一的下标 ，满足 ； 从下标 移动到下标 。
如果 $t左移动；如果 ，则记作一次向右移动。
请统计完成全部巡检后，向左移动和向右移动分别发生了多少次。
输入描述
第一行读入一个整数 （），表示检测点的数量。
第二行读入 个整数 ，它们构成一个 的排列。
输出描述
输出一行两个非负整数，依次表示整个巡检过程中向左移动的次数和向右移动的次数。
样例1
输入
52 4 1 5 3输出
2 2说明
各序号所在的下标依次为 。
因此移动过程为 ，其中 、 向左，共 次；另外两次移动向右，所以输出 2 2。
样例2
输入
63 6 1 5 2 4输出
3 2说明
序号 所在的位置依次为 ，移动轨迹为
。
其中有 次移动到更小的下标，有 次移动到更大的下标，因此答案为 3 2。
题解
解题思路
由于数组是一个排列，所以每个序号都只出现一次。
可以先预处理一个位置数组 ，其中 表示数字 在排列中的下标。
之后按照巡检顺序从 枚举到 ：
如果 ，说明从序号 移动到序号 时向左移动。 如果 ，说明这次向右移动。
因此只需要先记录每个数字的位置，再进行一次线性扫描即可。
使用的算法为排列逆映射与线性枚举。
复杂度分析
建立位置数组需要 的时间，统计移动方向也需要 的时间，因此总时间复杂度为 。
位置数组需要保存 个元素，因此空间复杂度为 。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defsolve(p): n = len(p)# pos[x] 表示数字 x 所在的位置 pos = [0] * (n + 1)for i in range(n): pos[p[i]] = i left = 0 right = 0# 按照 1 -> 2 -> ... -> n 的顺序移动for x in range(1, n):if pos[x + 1] < pos[x]: left += 1else: right += 1return left, rightdefmain(): n = int(input()) p = list(map(int, input().split())) left, right = solve(p) print(left, right)if __name__ == "__main__": main()第2题-监测样本偏离判定
题目内容
某监测系统积累了一批处于稳定状态下的历史传感数据，这些记录均可视为正常样本。现在系统收到一批新的监测记录，希望根据历史数据所形成的主要变化模式，判断新记录是否出现明显偏离。
请在仅使用 的前提下，实现一个基于 重建误差的异常检测方法，并对每个待检测样本给出判定结果。
已知参考数据中只包含正常样本，而待检测数据中可能同时存在正常样本和异常样本。整个处理过程必须严格按照下面的步骤进行。
1. 缺失值补全
设参考矩阵为 ，待检测矩阵为 。
对于第 列特征，计算参考矩阵该列所有非缺失元素的均值，记为 。
随后：
参考矩阵第 列中的缺失值全部使用 补全； 待检测矩阵第 列中的缺失值也必须使用相同的 补全。
补全后的两个矩阵仍记作 和 。
其中：
为参考样本数量； 为待检测样本数量； 为特征维度。
2. 标准化
使用 StandardScaler 对数据进行标准化。
StandardScaler 只能在参考矩阵 上执行 fit，之后分别对 和 执行 transform。
标准化后的矩阵分别记为 和 。
若参考数据第 个特征的均值和标准差分别为 、，则有：
以及：
注意，待检测数据不能单独计算均值或标准差。
3. PCA 投影与重建
仅使用标准化后的参考矩阵 训练 。
参数固定为：
n_components=0.95svd_solver='full'
这表示保留累计解释方差比达到或超过 所需要的最少主成分数量。
将 投影到得到的主成分空间后再执行逆变换，记重建结果为 。
使用同一个已经训练完成的 对 进行投影和逆变换，得到 。
整个过程中，不允许使用待检测数据重新训练或调整 。
4. 偏离分数
一个样本的偏离分数定义为它与 PCA 重建结果之间各维平方差之和。
对于第 个参考样本：
对于第 个待检测样本：
因此，全部参考样本对应的偏离分数组成：
5. 判定边界
使用全部参考样本的偏离分数计算判定边界 。
必须按照下面的方式得到：
np.percentile(D_ref, 95)
即：
对于第 个待检测样本，其输出标签定义为：
其中：
表示该样本判定为正常； 表示该样本判定为异常。
注意，当偏离分数恰好等于 时，该样本仍判定为正常。
输入描述
标准输入为 JSON，格式如下：
{"train": [[f11, f12, ..., f1d], [f21, f22, ..., f2d], ...],"test": [[g11, g12, ..., g1d], [g21, g22, ..., g2d], ...]}其中：
train：二维列表，大小为 ，其中所有样本均为正常样本；test：二维列表，大小为 ，包含需要判定的样本；每个特征值可能是整数、浮点数或 null；train与test的特征列数完全相同；； ； 。
输出描述
输出一个 JSON 数组，其中依次存放所有待检测样本的判定标签。
例如：
[0, 1, 0]其中：
表示正常； 表示异常。
标签的顺序必须与输入中 test 的样本顺序保持一致。（标签之间有空格）
补充说明
仅允许使用 ； 缺失值所使用的均值只能来自训练数据； StandardScaler和PCA均只能在训练数据上进行拟合；PCA 参数必须为 n_components=0.95、svd_solver='full'；判定边界必须使用 np.percentile(D_ref, 95)；不得改用 IsolationForest、One-Class SVM、RobustScaler等其他异常检测或预处理方法。
样例1
输入
{"train": [[1,2],[2,4.1],[3,5.9],[4,8.1],[5,10]],"test": [[2.5,5.0],[2.5,10.0],[3.0,null]]}输出
[0, 1, 0]说明
训练数据的两个特征具有较明显的共同变化趋势，因此 PCA 可以用较少的主成分描述其主要结构。
第一个待检测样本与训练数据表现出的变化关系接近，其重建偏离较小，因此输出 。
第二个样本的两个特征之间出现了明显不同于参考数据的关系，PCA 重建后的平方误差和超过训练误差的 分位数，因此输出 。
第三个样本的第二维为 null，需要先使用训练数据第二维特征的均值进行补全，再执行标准化和 PCA 重建。其最终偏离分数没有超过判定边界，因此输出 。
题解
解题思路
本题使用 重建误差进行异常检测。
训练集全部由正常样本组成，因此可以利用训练集学习正常数据的主要特征结构。如果一个测试样本与正常数据差异较大，那么经过 降维并重建后，它的重建误差通常也会更大。
具体按照以下步骤处理：
缺失值填充。
先计算训练集每一列的均值。训练集和测试集中的缺失值，都使用对应列的训练均值填充。
这样可以保证测试集不会参与任何统计量的计算。
标准化。
使用 StandardScaler，只在训练集上执行 fit，然后分别对训练集和测试集执行 transform。
训练 。
在标准化后的训练集上建立 PCA，参数固定为：
PCA(n_components=0.95, svd_solver='full')这样会自动选择累计解释方差比达到 所需的最少主成分。
之后分别将训练集和测试集进行：
transform -> inverse_transform得到对应的重建数据。
计算重建误差。
对于一个样本，将标准化后的原数据与重建数据对应位置作差，计算平方和：
分别得到所有训练样本和测试样本的重建误差。
确定异常阈值。
将所有训练样本的重建误差记为 ，按照题目要求使用：
np.percentile(E_train, 95)得到阈值 。
对于每个测试样本：
若重建误差大于 ，输出 ； 否则输出 。
需要特别注意，误差等于阈值时仍然属于正常样本，因此代码中必须使用严格的大于号 >。
复杂度分析
设训练样本数为 ，测试样本数为 ，特征数为 ，最终保留的主成分数量为 。
缺失值处理和标准化的时间复杂度为：
使用 svd_solver='full' 训练 时，需要进行完整奇异值分解，其时间复杂度可以表示为：
训练集和测试集进行投影、重建以及计算误差的时间复杂度为：
因此总体时间复杂度主要由 的完整奇异值分解决定。
空间复杂度主要用于保存训练集、测试集以及 的主成分矩阵，为：
本题中 、、 都很小，因此该复杂度完全可以满足要求。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
import jsonimport sysimport numpy as npfrom sklearn.preprocessing import StandardScalerfrom sklearn.decomposition import PCAdefdetect_anomaly(train, test):# 转为浮点数组，JSON 中的 null 会转换为 nan X = np.array(train, dtype=float) T = np.array(test, dtype=float)# 计算训练集每一列的均值 means = np.nanmean(X, axis=0)# 使用训练均值填充训练集缺失值 row, col = np.where(np.isnan(X)) X[row, col] = means[col]# 使用相同的训练均值填充测试集缺失值 row, col = np.where(np.isnan(T)) T[row, col] = means[col]# 标准化，只在训练集上拟合 scaler = StandardScaler() X_scaled = scaler.fit_transform(X) T_scaled = scaler.transform(T)# PCA 只在训练集上训练 pca = PCA(n_components=0.95, svd_solver='full') pca.fit(X_scaled)# PCA 投影并重建 X_rebuilt = pca.inverse_transform(pca.transform(X_scaled)) T_rebuilt = pca.inverse_transform(pca.transform(T_scaled))# 计算每个样本的重建误差 train_error = np.sum((X_scaled - X_rebuilt) ** 2, axis=1) test_error = np.sum((T_scaled - T_rebuilt) ** 2, axis=1)# 训练误差的 95% 分位数作为阈值 threshold = np.percentile(train_error, 95)# 严格大于阈值才判定为异常return (test_error > threshold).astype(int).tolist()defmain():# 读取 JSON 输入 data = json.loads(sys.stdin.read()) train = data["train"] test = data["test"]# 进行异常检测 answer = detect_anomaly(train, test)# 按 JSON 数组格式输出 print(json.dumps(answer))if __name__ == "__main__": main()
