OPPO

P5226.第2题-最小信号功率

第2题-最小信号功率 - problem_ide - CodeFun2000

学一下数学技巧

题意转化

$$ P-|i-c|\ge r_i \rightarrow P\ge r_i+|i-c| $$
绝对值不等式
$$ P\ge\max\left(\max_i(r_i+i)-c,\;\max_i(r_i-i)+c\right) $$
再分别取最大
$$ A=\max_i(r_i+i),\qquad B=\max_i(r_i-i) $$
整个问题瞬间变成
$$ \min_c \max(A-c,\ B+c) $$
所以要让两者的最大值尽可能小，最佳位置就是让二者尽量相等
$$ P_{\min}=\left\lceil\frac{A+B}{2}\right\rceil $$
进而得到 c
$$ c=\left\lfloor\frac{A-B}{2}\right\rfloor $$

P5221.第2题-监测样本偏离判定

第2题-监测样本偏离判定 - problem_ide - CodeFun2000

了解PCA的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import numpy as np
import json
import sys
from sklearn.preprocessing import StandardScaler # x - mu / sigma
from sklearn.decomposition import PCA

def main():
    data = json.loads(sys.stdin.read())

    train = data["train"]
    test = data["test"]

    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) # 从 X 中获得 mu 和 sigma
    T_scaled = scaler.transform(T)     # 做标准化，不重新计算均值与标准差

    # PCA 只在训练集上训练
    pca = PCA(n_components=0.95, svd_solver="full") # 创建 PCA 对象
    pca.fit(X_scaled)  # 从标准化后数据中学习 PCA 规则

    # PCA 投影并重建
    # transform 使用 pca 已经学到的规则，把 X_scaled 转换到 PCA 空间
    # inverse_transform 再把PCA空间数据映射回来
    X_rebuild = pca.inverse_transform(pca.transform(X_scaled))
    T_rebuild = pca.inverse_transform(pca.transform(T_scaled))

    # 计算每个样本的重建误差
    train_error = np.sum((X_scaled - X_rebuild)**2, axis= 1)
    test_error = np.sum((T_scaled - T_rebuild)**2, axis=1)

    # 训练误差的 95% 分位数作为阈值
    threshold = np.percentile(train_error, 95)
    ans = (test_error > threshold).astype(int).tolist()
    print(json.dumps(ans))

if __name__ == "__main__":
    main()

sklearn 逻辑：

1
2
3
4
5
model = Something(...)  # 创建工具 / 设置超参数
model.fit(X)            # 从 X 学参数
model.transform(X)      # 用学到的参数转换 X
model.fit_transform(X)  # 先学，再转换 X
model.inverse_transform(Z) # 把转换后的数据尽量映射回原来的空间

json 常用函数

函数 输入 输出
json.loads() JSON 字符串 Python 对象
json.dumps() Python 对象 JSON 字符串
json.load() JSON 文件 Python 对象
json.dump() Python 对象 JSON 文件