输入输出

单个按空格键分开

1
2
3
4
data = sys.stdin.read().strip().split() 
if not data:
    return
it = iter(data)

按行读(适用于不确定行数的)

1
2
3
4
lines = sys.stdin.read().strip().splitlines()

for line in lines:
    parts = line.split()

如果确定行数可以直接用input

输出数组

1
2
for row in arr:
    print(" ".join(map(str, row)))

Python 的 round() 不是传统四舍五入，而是“遇到 .5 舍到偶数”的银行家舍入

要做传统“四舍五入”，不要用 Python 内置 round()，推荐用 Decimal + ROUND_HALF_UP

1
2
3
4
from decimal import Decimal, ROUND_HALF_UP
def round_half_up(x):
    return Decimal(str(x)).quantize(Decimal('1'), rounding=ROUND_HALF_UP) # 返回类型是Decimal类，还需要转str/数字
# 不要用 Decimal(x)，要转一次str，不然会有float二进制误差

np库

创建数组

  • np.zeros(size)：全 0 数组
  • np.full(size, val)：填充值数组

对角矩阵

1
2
3
4
5
np.diag([1, 2, 3])   # 创建对角矩阵
np.diag(A)           # 提取矩阵 A 的对角线
np.eye(n)            # 创建 n x n 单位矩阵
np.triu(np.ones((m, h))) # 全1上三角矩阵 / upper triangular
np.tril(np.ones((m, h))) # 全1下三角矩阵 / lower triangular

形状变换

  • .reshape(-1) ：把数组拉平成一维数组，长度自动推断

向量距离

  • np.linalg.norm(diff, axis=2)：沿第 2 维计算欧氏距离
  • np.bincount(labels, minlength=k)：统计非负整数数组中每个整数出现次数，从 0 开始，统计到k-1，长度为k
  • np.argmin(distance, axis=1)：返回每一行最小值的位置
  • np.argsort(x)：返回排序后的下标

条件筛选

  • X[labels == k]：取满足条件的行，label==k用于创造mask
  • X_new = np.delete(X, index, axis=0)：删除index行，可为列表

拼接：np.concatenate() 沿已有轴拼，注意要带个[]

1
c = np.concatenate([a, b], axis=1)

类型转换：X.astype()，方便修改输出形式

矩阵计算

  • a @ b：矩阵乘法，等价于 np.matmul(a, b)
    $$
    (m, n) @ (n, p) \rightarrow (m, p)
    $$

  • * 是逐元素乘法

  • np.dot(a, b)：一维时是点积/内积，二维时是矩阵乘法

  • np.outer(a, b)：外积，把两个向量变成一个矩阵

    输入(m,) (n,) 输出 (m, n)

  • rank = np.linalg.matrix_rank(A) 矩阵的秩

  • A_inv = np.linalg.inv(A) 矩阵的逆

  • np.linalg.eig(A) 特征值和特征向量

  • np.linalg.cond(A) 条件数

哈希表

创建字典：

1
dic = {}

用in判断key是否存在

访问 value 可以用 get

1
2
dic.get("apple", 0) # 如果 "apple" 不存在，返回 0
dic[word] = dic.get(word, 0) + 1 # 计数

删除 key

1
2
if dic.get(word) == 0:
    del dic[word]
1
for k in dic: # 遍历 key
1
for v in dic.values(): # 遍历 value

遍历key

1
2
for k in dic:
    print(k)

遍历 key 和 value：

1
2
for k, v in dic.items():
    print(k, v)

sorted 返回的是一个 list，需要接收，不动原来的dict，因为dict本身无序

dict.items() 提供的是 (key, value) 的键值对序列（可迭代对象），直接对 dict 排序只会得到 键的序列

按 key

1
sorted(d, key=lambda x: x[0])

按 value，需要用.items()提取出来

1
2
3
sorted(dic.items(), key=lambda x: x[1]) # 升序
sorted(dic.items(), key=lambda x: -x[1]) # 降序
sorted(dic.items(), key=lambda x: (-x[1], x[0])) # 按 value 降序，value 相同按 key 升序

提取排序后的内容

1
2
keys = [k for k, v in items]
values = [v for k, v in items]

dfs

DFS 有几种常见写法：

  1. 返回值型 DFS：return 数据

    适合：每个子问题有明确答案，当前节点 / 当前状态的答案是多少？

    比如树的子树和

    1
    2
    3
    4
    5
    6
    7
    8
    def dfs(node):
        if node is None:
            return 0

        left = dfs(node.left)
        right = dfs(node.right)

        return left + right + node.val

    记忆化搜索，比如0-1背包问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    from functools import cache

    @cache
    def dfs(i, budget):
        if i == n:
            return 0

        return max(
            dfs(i + 1, budget), # 不选
            dfs(i + 1, budget - cost[i]) + value[i] # 选
        )

    判断标准：父递归是否需要子递归的结果？

    需要 -> return

    不需要 -> 不一定 return

  2. 全局更新型 DFS：nonlocal ans

    适合：遍历所有方案，在搜索过程中更新全局最优答案

  3. 什么时候用 path

    具体选了哪些东西 / 走了哪条路 / 当前排列是什么？

    枚举所有子集

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    path = []
    ans = []

    def dfs(i):
        if i == n:
            ans.append(path[:]) # 必须 path[:]，不能直接 ans.append(path)
            return

        # 不选 i
        dfs(i + 1)

        # 选 i
        path.append(i)
        dfs(i + 1)
        path.pop()

P4963.第2题-LLM 多源语料分级清洗预算分配

第2题-LLM 多源语料分级清洗预算分配 - problem_ide - CodeFun2000

  • 每一层都可以作为起点，可以return数值
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
from functools import cache
def main():
    N, B, T = map(int, input().split())
    w = []
    r = []
    c = []
    t = []
    for _ in range(N):
        data = list(map(float, input().split()))
        w.append(data[0])
        r.append(data[1])
        c.append(data[2])
        t.append(data[3])

    # 每种清洗方案: (预算倍数, 算力倍数, 污染率倍率)
    options = [
        (0, 0, 1.0),  # 不清洗
        (1, 1, 0.6),  # 清洗 1
        (3, 2, 0.2),  # 清洗 2
        (6, 3, 0.0),  # 清洗 3
    ]
    @cache
    def dfs(i, use_B, use_T):
        if use_B > B or use_T > T:
            return float("inf")

        if i == N:
            return 0.0

        base_risk = w[i] * r[i]

        ans = float("inf")
        for kb, kt, kr in options:
            ans = min(
                ans,
                base_risk * kr
                + dfs(
                    i + 1,
                    use_B + kb * c[i],
                    use_T + kt * t[i]
                )
            )

        return ans

    ans = dfs(0, 0.0, 0.0)
    print(f"{ans:.6f}")

if __name__ == "__main__":
    main()

动态规划

P4568.第2题-模型推理量化加速优化问题

第2题-模型推理量化加速优化问题 - problem_ide - CodeFun2000

从每一层里选一个方案，所以状态天然是dp[i][loss]，表示前i层累计损失不超过/等于 t 时的最小内存占用

注意点：

  • 缩放因子为S，将阈值转为整数容量，方便dp
    $$
    dp[i][new_loss] = \min(dp[i][new_loss],dp[i-1][old_loss]+mem_j)
    $$
    $j$ 代表可选方案
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
53
import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    p = 0
    L = int(data[0])
    p+=1
    T = float(data[1])
    p+=1

    S = 100
    Itotal_loss = int(round(S*T)) # 化整后的总损失

    layers = []

    for _ in range(L):
        K = int(data[p])
        p+=1
        options = []
        for _ in range(K):
            bit_desc = data[p]  # 记录bit选择
            p+=1
            loss = float(data[p]) 
            p+=1
            mem = float(data[p]) # 记录选择的内存消耗
            p+=1

            Iloss = int(round(S*loss))  # 化整后的选择损失
            options.append((Iloss, mem))
        layers.append(options)

    INF = float('inf')
    
    dp = [[INF] * (Itotal_loss + 1) for _ in range(L + 1)]
    dp[0][0] = 0.0

    for i in range(1, L+1):
        for Iloss, mem in layers[i-1]:
            if Iloss <= Itotal_loss:
                for old_loss in range(Itotal_loss - Iloss+ 1):
                    new_loss = old_loss + Iloss
                    dp[i][new_loss] = min(
                        dp[i][new_loss],
                        dp[i-1][old_loss] + mem
                    )

    ans = min(dp[L])
    print(f"{ans:.2f}")
    
if __name__ == "__main__":
    solve()

递归写法，选哪个

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
import sys
from functools import cache

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    L = int(next(it))
    S = 100
    T = round(float(next(it)) * S)
    layers = []
    for i in range(L):
        K = int(next(it))
        options = []
        for _ in range(K):
            _ = next(it)
            loss = round(float(next(it)) * S)
            mem = float(next(it))
            options.append((loss, mem))
        layers.append(options)

    @cache
    def dfs(index, loss: int):
        if loss > T:
            return float("inf")
        if index == L:
            return 0
        n = len(layers[index])
        options = layers[index]
        return min(dfs(index+1, loss + options[i][0]) + options[i][1] for i in range(n))

    min_mem = dfs(0, 0)

    print(f"{min_mem:.2f}")

if __name__ == "__main__":
    main()

P4274.第2题-最大能量路径

第2题-最大能量路径 - problem_ide - CodeFun2000

注意点：

  • 怎么实现卷积

  • 怎么实现边缘pad

  • 最优路径三条
    $$
    dp[i][j] = \max(dp[i][j-1], dp[i-1][j-1],dp[i+1][j-1]) + score[i][j]
    $$
    注意要满足i-1或者i+1不越界时才有三项对比，越界了就抛弃那一项

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import sys

def conv2d_padding_zero(img, kernel):
    img = np.asarray(img, dtype=float)
    kernel = np.asarray(kernel, dtype=float)

    H, W = np.shape(img)
    KH, KW = np.shape(kernel)

    pad_top = KH // 2
    pad_bottom = KH - 1 - pad_top

    pad_left = KW // 2
    pad_right = KW - 1 - pad_left

    img_pad = np.pad(
        img,
        ((pad_top, pad_bottom), (pad_left, pad_right)),
        mode="constant",
        constant_values=0
    )

    energy = np.zeros((H, W), dtype=float)

    for i in range(H):
        for j in range(W):
            window = img_pad[i:i + KH, j:j + KW]
            energy[i, j] = np.sum(window * kernel)

    return energy

def max_energy_path(energy):
    H, W = len(energy), len(energy[0])
    dp = [[0.0]* W for _ in range(H)]
    for i in range(H):
        dp[i][0] = energy[i][0]

    for j in range(1, W):
        for i in range(0, H):
            # 当前位置可以从正左方来
            dp[i][j] = max(dp[i][j],dp[i][j-1]+energy[i][j])
            # 当前位置可以从左上方来
            if i-1>=0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+energy[i][j])
            # 当前位置可以从左下方来
            if i+1<H:
                dp[i][j] = max(dp[i][j], dp[i+1][j-1]+energy[i][j])

    ans = dp[0][W-1]
    for i in range(1, H):
        ans = max(ans, dp[i][W-1])

    return ans

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    idx = 0
    H = int(data[idx])
    idx += 1
    W = int(data[idx])
    idx += 1
    KH = int(data[idx])
    idx += 1
    KW = int(data[idx])
    idx += 1

    img = []
    for _ in range(H):
        row = []
        for _ in range(W):
            row.append(int(data[idx]))
            idx += 1
        img.append(row)

    kernel = []
    for _ in range(KH):
        row = []
        for _ in range(KW):
            row.append(int(data[idx]))
            idx += 1
        kernel.append(row)

    energy = conv2d_padding_zero(img, kernel)
    ans  = max_energy_path(energy)
    print(f"{ans:.1f}")

if __name__ == '__main__':
    solve()

P3713.第3题-大模型分词

第3题-大模型分词 - problem_ide - CodeFun2000

  • 将匹配的内容以字典的形式读取，方便后续查找和匹配
  • 需要记录上一个匹配状态，也就是上一个能拆分的词

第一版写法，能通过

问题在于：后续转移分数依赖上一个词，所以对于同一个位置 i，只保留一个最大 dp[i] 会丢状态

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
53
54
55
import sys

def calculate_max_score(text, words, rules):
    n = len(text)
    dp = [float('-inf')] * (n + 1)
    prev = [None] * (n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(i):
            word = text[j:i]
            if word in words and dp[j]!=float('-inf'):
                score = words[word]
                if prev[j] and (prev[j],word) in rules:
                    score += rules[(prev[j],word)]
                if dp[j] + score >= dp[i]:
                    dp[i] = dp[j] + score
                    prev[i] = word

    return dp[n] if dp[n]!=float('-inf') else 0

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    idx = 0
    text = data[idx]
    idx += 1
    n = int(data[idx])
    idx += 1

    words = {}
    for _ in range(n):
        word = data[idx]
        idx += 1
        score = int(data[idx])
        idx += 1
        words[word] = score
    m = int(data[idx])

    rules = {}
    idx += 1
    for _ in range(m):
        word1 = data[idx]
        idx += 1
        word2 = data[idx]
        idx += 1
        score = int(data[idx])
        idx += 1
        rules[(word1, word2)] = score

    max_score = calculate_max_score(text, words, rules)
    print(max_score)

if __name__ == '__main__':
    solve()

反例

1
2
3
4
5
6
7
8
abc
4
a 0
b 100
ab 99
c 0
1
ab c 100

正确切分应该是：

1
ab + c

得分：

1
99 + 0 + 100 = 199

但代码在位置 2 会认为：

1
2
a + b = 100
ab = 99

所以它保留：

1
2
dp[2] = 100
prev[2] = "b"

然后接 "c" 时，因为没有规则：

1
("b", "c")

所以只能得到：

1
100

这不对，所以需要给dp加上最后一个词状态dp[i][last]，这样才不会丢掉“最后一个词不同”的状态

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import sys

def calculate_max_score(text, words, rules):
    n = len(text)

    # dp[i] 是一个字典：
    # key   = 最后一个词
    # value = text[:i] 以该词结尾时的最大得分
    dp = [dict() for _ in range(n + 1)]

    # 空前缀，尚无上一个词，得分为 0
    dp[0][None] = 0

    # 小优化：只枚举不超过词典最大词长的子串
    max_len = 0
    for w in words:
        max_len = max(max_len, len(w))

    # 枚举右端点 i，尝试把 text[j:i] 作为最后一个词
    for i in range(1, n + 1):
        start = max(0, i - max_len)

        for j in range(start, i):
            word = text[j:i]

            # 当前子串必须是已知词元
            if word not in words:
                continue

            # 从所有能完整切分 text[:j] 的状态转移
            # 如果空字典，也是就dp[j]不可分，就不会进循环
            for prev_word, old_score in dp[j].items():
                score = old_score + words[word]

                # 如果存在上一个词，则尝试加入转移分数
                if prev_word is not None:
                    score += rules.get((prev_word, word), 0)

                # 更新 text[:i] 以 word 结尾时的最大得分
                if word not in dp[i] or score > dp[i][word]:
                    dp[i][word] = score

    # 无法完整切分 text
    if not dp[n]:
        return 0

    # 最后一词可以是任意词，取最大得分
    return max(dp[n].values())


def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    idx = 0
    text = data[idx]
    idx += 1
    n = int(data[idx])
    idx += 1

    words = {}
    for _ in range(n):
        word = data[idx]
        idx += 1
        score = int(data[idx])
        idx += 1
        words[word] = score
    m = int(data[idx])

    rules = {}
    idx += 1
    for _ in range(m):
        word1 = data[idx]
        idx += 1
        word2 = data[idx]
        idx += 1
        score = int(data[idx])
        idx += 1
        rules[(word1, word2)] = score

    max_score = calculate_max_score(text, words, rules)
    print(max_score)

if __name__ == '__main__':
    solve()

P4625.第2题-大模型训练显存优化算法

第2题-大模型训练显存优化算法 - problem_ide - CodeFun2000

注意点：

  • dp 完全展开的话会超时，需要压一下dp范围
  • 注意不要忘记不选择的情况

dp[i][j]其中j代表的是容量

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
53
54
55
import sys

def calulate_cost(M, storage_space, cost):
    INF = float('inf')
    if sum(storage_space) < M:
        return INF
    N = len(storage_space)

    dp = [[INF] * (M+1) for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        space = storage_space[i-1]
        cst = cost[i-1]
        for j in range(M + 1):
            # 不选择第 i 个张量
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            # 选第 i 个张量
            if dp[i - 1][j] != INF:
                next_space = min(M, j + space)
                dp[i][next_space] = min(
                    dp[i][next_space],
                    dp[i-1][j] + cst
                )
    return dp[N][M]

def solve():
    data = sys.stdin.read().split()
    idx = 0
    M = int(data[idx])
    idx += 1
    N = int(data[idx])
    idx += 1
    storage_space = []
    for _ in range(N):
        storage_space.append(int(data[idx]))
        idx += 1
    swap_cost = []
    for _ in range(N):
        swap_cost.append(int(data[idx]))
        idx += 1
    recalulate_cost = []
    for _ in range(N):
        recalulate_cost.append(int(data[idx]))
        idx += 1
    cost = []
    for i in range(N):
        cost.append(min(swap_cost[i], recalulate_cost[i]))

    min_cost = calulate_cost(M, storage_space, cost)

    print(min_cost) if min_cost!=float('inf') else print("error")

if __name__ == '__main__':
    solve()

但其实这题的思路就是选或不选，用dfs很简单

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
53
54
55
56
import sys
from functools import cache


def calulate_cost(M, storage_space, cost):
    INF = float('inf')
    if sum(storage_space) < M:
        return INF

    N = len(storage_space)
    @cache
    def dfs(index, need):
        if need <= 0:
            return 0 
        if index == N:
            return INF
        not_choose = dfs(index+1, need)
        choose = cost[index] + dfs(
            index+1,
            max(0, need-storage_space[index])
        )
        return min(not_choose, choose)

    return dfs(0, M)

def solve():
    data = sys.stdin.read().split()
    idx = 0
    M = int(data[idx])
    idx += 1
    N = int(data[idx])
    idx += 1
    storage_space = []
    for _ in range(N):
        storage_space.append(int(data[idx]))
        idx += 1
    swap_cost = []
    for _ in range(N):
        swap_cost.append(int(data[idx]))
        idx += 1
    recalulate_cost = []
    for _ in range(N):
        recalulate_cost.append(int(data[idx]))
        idx += 1
    cost = []
    for i in range(N):
        cost.append(min(swap_cost[i], recalulate_cost[i]))

    min_cost = calulate_cost(M, storage_space, cost)

    print(min_cost) if min_cost != float("inf") else print("error")


if __name__ == "__main__":
    solve()

P4539.第3题-RAG系统最大收益

第3题-RAG系统最大收益 - problem_ide - CodeFun2000

注意点：

  • 注意边界的写法
  • 如果之前没更新过，写在初始化位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def main():
    n, d = map(int, input().split())
    update_cost = list(map(int, input().split()))
    query_reward = list(map(int, input().split()))
    dp = [[float("-inf")] * (n + 1) for _ in range(n + 1)]
    # 之前没更新过，收益始终为0
    for i in range(n + 1):
        dp[i][0] = 0

    for i in range(1, n + 1):
        # 情况 1：第 i 天选择更新
        dp[i][i] = max(dp[i - 1]) - update_cost[i - 1] + query_reward[i - 1]
        # 情况 2：第 i 天不选择更新
        for T in range(1, i):
            if i - T >= d:  # 超出有效期，不获得查询收益，但状态可以保留
                dp[i][T] = dp[i - 1][T]
            else:  # 在有效期内, 可以获得查询收益
                dp[i][T] = dp[i - 1][T] + query_reward[i - 1]

    return max(dp[n])

if __name__ == "__main__":
    main()

能通过80%，复杂度太高了，但是好写

P4569.第3题-AIGC缓存复用加速策略

第3题-AIGC缓存复用加速策略 - problem_ide - CodeFun2000

在 0...i 这 i+1 个位置里，最多能选 (i + 2) // 2 个互不相邻元素

T个步骤，首先第一个步骤必须不能跳过，所以其实就转化为后面T-1个步骤里选k个不相邻的步骤，对应loss也是T-1的长度

dfs转为选或不选问题，很直观

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
import sys
from functools import cache


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    T = int(next(it))
    k = int(next(it))
    loss = [int(next(it)) for _ in range(T-1)]
    n = len(loss)

    if k == 0:
        print(0)
        return

    # 长度为 n 的数组中，最多能选 ceil(n / 2) 个不相邻元素
    if k > (n + 1) // 2:
        print(-1)
        return

    @cache
    def dfs(i, remain):
        if remain == 0:
            return 0

        if i < 0:
            return float("inf")

        # 剩余位置不够选
        if remain > (i + 2) // 2:
            return float("inf")

        choose = loss[i] + dfs(i - 2, remain - 1)
        not_choose = dfs(i - 1, remain)

        return min(choose, not_choose)

    ans = dfs(n-1, k)
    print(ans)

if __name__ == "__main__":
    main()

Kmeans

普通 K-means 模板

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
import numpy as np


def kmeans(X, K, T=100, eps=1e-6):
    """
    X: (N, D), N 个样本，每个样本 D 维
    K: 聚类数量
    T: 最大迭代次数
    eps: 收敛阈值
    """
    N, D = X.shape

    # 1. 选择前 K 个样本作为初始中心
    centers = X[:K].copy()

    for _ in range(T):
        old_centers = centers.copy()

        # 2. 计算每个样本到每个中心的平方欧氏距离
        # None用来扩维度
        # X[:, None, :]       -> (N, 1, D)
        # centers[None, :, :] -> (1, K, D)
        # diff                -> (N, K, D)
        diff = X[:, None, :] - centers[None, :, :] 
        dist = np.linalg.norm(diff, axis=2)  # (N, K)

        # 3. 每个样本分配给最近中心
        labels = np.argmin(dist, axis = 1)  # (N,)

        # 4. 更新中心
        for k in range(K):
            members = X[labels == k]

            if len(members) > 0:
                centers[k] = np.mean(members, axis=0)

        # 5. 收敛判断
        shift = np.linalg.norm(centers - old_centers)

        if shift < eps:
            break

    # 用最终 centers 重新分配一次 labels
    diff = X[:, None, :] - centers[None, :, :]
    dist = np.linalg.norm(diff, axis=2)
    labels = np.argmin(dist, axis=1)

    counts = np.bincount(labels, minlength=K)

    return labels, centers, counts

P3842.第2题-Yolo检测器中的anchor聚类

第2题-Yolo检测器中的anchor聚类 - problem_ide - CodeFun2000

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
import numpy as np


def iou_wh(boxes, centers):
    """
    boxes:   shape (N, 2)   -> [w, h]
    centers: shape (K, 2)   -> [W, H]

    return:
        iou matrix, shape (N, K)
    """
    # 扩展维度后做广播
    bw = boxes[:, 0:1]      # (N, 1)
    bh = boxes[:, 1:2]      # (N, 1)
    cw = centers[:, 0]      # (K,)
    ch = centers[:, 1]      # (K,)

    inter = np.minimum(bw, cw) * np.minimum(bh, ch)   # (N, K)
    union = bw * bh + cw * ch - inter                 # (N, K)

    return inter / (union + 1e-16)


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    T = int(next(it))

    boxes = np.array([[int(next(it)), int(next(it))] for _ in range(N)], dtype=np.float64)

    # 1. 稳定初始化：直接取前 K 个框作为初始中心
    centers = boxes[:K].copy()

    for _ in range(T):
        old_centers = centers.copy()

        # 2. 分配阶段：d = 1 - IOU，取距离最小 <=> IOU 最大
        iou_mat = iou_wh(boxes, centers)          # (N, K)
        distances = 1.0 - iou_mat
        labels = np.argmin(distances, axis=1)

        # 3. 更新阶段：簇内宽高均值，并向下取整；空簇保持不变
        new_centers = centers.copy()
        for k in range(K):
            members = boxes[labels == k]
            if len(members) > 0:
                new_centers[k] = np.floor(np.mean(members, axis=0))

        # 4. 终止条件：新旧中心配对 d 值之和 < 1e-4
        center_iou = iou_wh(old_centers, new_centers)   # shape (K, K)
        # 这里只取对应位置 (k, k)，即旧中心k 与 新中心k 的 IOU
        diag_iou = np.diag(center_iou) # 二维转一维
        shift = np.sum(1.0 - diag_iou)

        centers = new_centers
        if shift < 1e-4:
            break

    # 5. 输出：按面积从大到小排序
    centers = centers.astype(np.int64)
    areas = centers[:, 0] * centers[:, 1]
    order = np.argsort(-areas)
    centers = centers[order]

    out = []
    for w, h in centers:
        out.append(f"{w} {h}")

    print("\n".join(out))


if __name__ == "__main__":
    main()

P4475.第2题-终端款型聚类识别

第2题-终端款型聚类识别 - problem_ide - CodeFun2000

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
import sys
import numpy as np

def kmeans(X, K, T):
    centers = X[:K].copy()

    for _ in range(T):
        old_centers = centers.copy()

        diff = X[:, None,:] - centers[None,:,:]
        distances = np.linalg.norm(diff, axis=2)
        labels = np.argmin(distances, axis=1)

        for k in range(K):
            members = X[labels == k]
            if len(members) >0:
                centers[k] = members.mean(axis=0)

        shift = np.linalg.norm(centers - old_centers)
        if shift < 1e-8:
            break

    counts = np.bincount(labels, minlength=K)

    return labels, centers, counts

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    K = int(next(it))
    m = int(next(it))
    n = int(next(it))
    X = np.array(
        [[float(next(it)) for _ in range(4)] for _ in range(m)],
        dtype=np.float64
    )
    _, _, counts = kmeans(X, K, n)
    # 不破坏原来的计数
    sorted_counts = np.sort(counts)
    print(" ".join(map(str, sorted_counts)))

if __name__ == "__main__":
    main()

如果要有序输出 标签 + 数量 

1
2
3
order = np.argsort(counts) # 按数量返回标签排序
for k in order:
    print(f"cluster {k}: {counts[k]}")

P4571.第2题-网络流量分析

第2题-网络流量分析 - problem_ide - CodeFun2000

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
import numpy as np

def main():
    k = int(input())
    centers = np.array(
        [list(map(float, input().split())) for _ in range(k)],
        dtype=np.float64
    )
    T = int(input())
    m = int(input())
    X = np.array(
        [list(map(float, input().split())) for _ in range(m)],
        dtype=np.float64
    )
    for _ in range(T):
        diff = X[:, None, :] - centers[None, :, :]
        dist = np.linalg.norm(diff, axis=2)
        labels = np.argmin(dist, axis = 1)
        for i in range(k):
            members = X[labels == i]
            if len(members) > 0:
                centers[i] = np.mean(members, axis=0)

    for center in centers:
        print(" ".join(f"{x:.2f}" for x in center))

if __name__ == "__main__":
    main()

P3791.第2题-无线网络优化中的基站聚类分析

第2题-无线网络优化中的基站聚类分析 - problem_ide - CodeFun2000

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import numpy as np
from decimal import Decimal, ROUND_HALF_EVEN
def half_even(x):
    return Decimal(str(x)).quantize(
        Decimal("0.00"),
        rounding=ROUND_HALF_EVEN
    )
def main():
    n, K = map(int, input().split())
    # 读取二维点，使用 float，避免中心点均值被截断
    X = np.array(
        [list(map(float, input().split())) for _ in range(n)],
        dtype=np.float64
    )
    # 初始中心取前 K 个点
    centers = X[:K].copy() # 注意copy

    for _ in range(100):
        old_centers = centers.copy()
        # 计算每个点到每个中心的距离，shape: (n, K)
        dist = np.linalg.norm(
            X[:, None, :] - centers[None, :, :],
            axis=2
        )
        # 每个点分配到最近的中心
        label = np.argmin(dist, axis=1)
        # 更新每个簇的中心
        for k in range(K):
            members = X[label == k]
            if len(members) > 0:
                centers[k] = np.mean(members, axis=0)

        # 判断中心是否收敛
        shift = np.linalg.norm(centers - old_centers, axis=1)
        if np.all(shift < 1e-6):
            break

    # 构造每个簇包含的点下标
    idx = np.arange(n)
    clusters = []
    for k in range(K):
        clusters.append(idx[label == k])

    # 计算所有点两两之间的距离，shape: (n, n)
    dist_X = np.linalg.norm(
        X[:, None, :] - X[None, :, :],
        axis=2
    )
    point_score = np.zeros(n)

    for i in range(n):
        label_i = label[i]
        same_cluster = clusters[label_i]

        # 计算 a：点 i 到同簇其他点的平均距离
        if len(same_cluster) <= 1:
            a = 1.0
        else:
            other = same_cluster[same_cluster != i]
            a = np.mean(dist_X[i, other])

        # 计算 b：点 i 到最近其他簇的平均距离
        b = float("inf")

        for k in range(K):
            if k == label_i:
                continue

            if len(clusters[k]) == 0:
                continue

            avg_dist = np.mean(dist_X[i, clusters[k]])
            b = min(b, avg_dist)

        # 计算 silhouette score
        if b == float("inf"):
            s = 0.0
        else:
            s = (b - a) / max(a, b)

        point_score[i] =s

    # 计算每个簇的平均 silhouette score
    clusters_score = np.zeros(K)

    for k in range(K):
        if len(clusters[k]) == 0:
            # 空簇不参与最小值选择
            clusters_score[k] = float("inf")
        else:
            clusters_score[k] = np.mean(point_score[clusters[k]])
            
    # 找平均 silhouette score 最低的簇
    min_score_idx = np.argmin(clusters_score)

    # 输出该簇中心
    new_p = centers[min_score_idx]

    print(f"{half_even(new_p[0])},{half_even(new_p[1])}")

if __name__ == "__main__":
    main()

模拟

P3712.第2题-大模型Attention模块开发

第2题-大模型Attention模块开发 - problem_ide - CodeFun2000

注意矩阵乘法的写法

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
import sys
import numpy as np

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    h = int(next(it))
    X = np.ones((n, m))
    W = np.triu(np.ones((m,h)))
    Q = X @ W
    K = X @ W
    V = X @ W

    M = ((Q @ K.T)/np.sqrt(h))
    Attn = M / M.sum(axis=1, keepdims=True)
    Y = Attn @ V

    print(f"{round(np.sum(Y))}")

if __name__ == '__main__':
    main()

P3553.第2题-大模型训练MOE场景路由优化算法

第2题-大模型训练MOE场景路由优化算法 - problem_ide - CodeFun2000

  • 利用元组来存储编号，方便回溯
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
import sys
import numpy as np


def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    p = int(next(it))
    k = int(next(it))
    prob = [float(next(it)) for _ in range(n)]
    if n%m or p>m:
        print("error")
        return
    group_size = n // m
    if k > group_size*p:
        print("error")
        return
    group = []
    for i in range(m):
        start = i * group_size
        end = (i + 1) * group_size
        max_prob = max(prob[start:end])
        group.append((max_prob, i))

    group.sort(key = lambda x: (-x[0], x[1]))
    select_group = set(i for _, i in group[:p])

    candidates = []
    for group_id in select_group:
        start = group_id*group_size
        end = (group_id+1)*group_size

        for expert_id in range(start, end):
            candidates.append((prob[expert_id], expert_id))

    candidates.sort(key = lambda x: (-x[0], x[1]))
    select_experts = [expert_id for _, expert_id in candidates[:k]]

    select_experts.sort()

    print(" ".join(map(str, select_experts)))

if __name__ == '__main__':
    main()

P4938.第2题-LLM 基石 - BPE 分词算法模拟

第2题-LLM 基石 - BPE 分词算法模拟 - problem_ide - CodeFun2000

注意：

  • turple的排序
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
53
54
55
def bpe(k, s):
    # 初始时，每个字符都是一个独立的 Token
    arr = list(s)

    # 最多执行 k 轮合并
    for _ in range(k):
        # 如果当前 Token 数量不足 2，则不存在相邻对
        if len(arr) < 2:
            break

        cnt = {}

        # 统计所有相邻 Token 对的出现次数
        for i in range(len(arr) - 1):
            p = (arr[i], arr[i + 1])
            cnt[p] = cnt.get(p, 0) + 1

        best = None
        best_cnt = 0

        # 选择频率最高的相邻对，频率相同则选择字典序最小的
        for p in cnt:
            if cnt[p] > best_cnt:
                best_cnt = cnt[p]
                best = p
            elif cnt[p] == best_cnt and p < best:
                best = p

        # 如果最高频率为 1，则提前终止
        if best_cnt == 1:
            break

        new_arr = []
        i = 0

        # 从左到右贪心合并所有最佳相邻对
        while i < len(arr):
            if i + 1 < len(arr) and arr[i] == best[0] and arr[i + 1] == best[1]:
                new_arr.append(arr[i] + arr[i + 1])
                i += 2
            else:
                new_arr.append(arr[i])
                i += 1
        arr = new_arr
    return arr

def main():
    k = int(input().strip())
    s = input().strip()

    ans = bpe(k, s)
    print(" ".join(ans))

if __name__ == "__main__":
    main()

list 排序用法

list.sort() 列表原地排序方法，默认升序，加reverse=True为降序

key 接收一个函数，这个函数对每个元素计算一个“排序依据”

可以用 lambda 自定义排序规则

多关键字排序：返回一个元组，这是最常用、最重要的用法

1
data.sort(key=lambda x: (-x[0], x[1]))
  • reverse=True：整体反转
  • -x[0]：只让第一个字段降序

排序字符串如果想忽略大小写

1
s.sort(key=str.lower)

卷积

无 padding、无 dilation 时
$$
H_{\text{out}}=
\left\lfloor
\frac{H_{\text{in}}-K_h}{s_h}
\right\rfloor + 1
\qquad W_{\text{out}}

\left\lfloor
\frac{W_{\text{in}}-K_w}{s_w}
\right\rfloor + 1
$$
对输出位置 (i, j)，实际输入窗口左上角是

1
2
h_start = i * stride_h
w_start = j * stride_w

无 dilation 时输出大小
$$
H_{\text{out}}

\left\lfloor
\frac{H_{\text{in}}+2p-K_h}{s_h}
\right\rfloor + 1
$$
如果 stride = 1，想让输出高度等于输入高度
$$
p = \frac{K_h-1}{2}
$$

1
2
3
4
5
6
padded_img = np.pad(
    img,
    pad_width=((pad_top, pad_bottom), (pad_left, pad_right)),
    mode="constant",
    constant_values=0
)

如果没有pad则

1
out_h, out_w = img_h - k_h +1, img_w - k_w +1

dilation 控制卷积核内部采样点之间的间隔

普通卷积 dilation = 1，比如3*3

1
2
3
x x x
x x x
x x x

如果 dilation = 2，则 kernel 在输入采样位置变为

1
2
3
4
5
x . x . x
. . . . .
x . x . x
. . . . .
x . x . x

有效卷积核大小是
$$
K_{\text{eff}} = d(K-1)+1
$$
通用输出尺寸公式
$$
H_{\text{out}} =
\left\lfloor
\frac{H_{\text{in}}+2p_h-K_{\text{eff},h}}{s_h}
\right\rfloor + 1
\qquad W_{\text{out}}

\left\lfloor
\frac{W_{\text{in}}+2p_w-K_{\text{eff},w}}{s_w}
\right\rfloor + 1
$$

P4939.第3题-2D 单通道空洞卷积（Dilated Convolution）底层实现

第3题-2D 单通道空洞卷积（Dilated Convolution）底层实现 - problem_ide - CodeFun2000

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
53
54
55
import numpy as np


def main():
    H, W = map(int, input().split())
    img = np.array(
        list(map(int, input().split())),
        dtype=int
    ).reshape((H,W))
    K = int(input())
    kernel = np.array(
        list(map(int, input().split())),
        dtype=int
    ).reshape((K,K))
    stride = int(input())
    pad = int(input())
    d = int(input())

    K_eff = K + (K-1) * (d-1)
    H_out = (H + 2*pad - K_eff)//stride + 1
    W_out = (W + 2*pad - K_eff)//stride + 1

    # print(H_out, W_out)
    img_pad = np.pad(
        img,
        ((pad, pad), (pad, pad)),
        mode="constant",
        constant_values=0
    )
    out = np.zeros((H_out, W_out), dtype=int)

    for i in range(H_out):
        for j in range(W_out):
            h_start = i * stride
            w_start = j * stride
            # 直接切片
            # patch = img_pad[
            #     h_start : h_start + K_eff : d,
            #     w_start : w_start + K_eff : d
            # ]
            patch = np.zeros((K, K), dtype=int)

            for ik in range(K):
                for jk in range(K):
                    patch[ik, jk] = img_pad[
                        h_start + ik * d,
                        w_start + jk * d
                    ]
            out[i, j] = np.sum(patch * kernel)

    for row in out:
        print(" ".join(map(str, row)))

if __name__ == "__main__":
    main()

P3493.第2题-Group卷积实现

第2题-Group卷积实现 - problem_ide - CodeFun2000

普通卷积：每个输出通道看所有输入通道

假设输入有 4 个通道：

1
输入通道: x0, x1, x2, x3

输出有 2 个通道：

1
输出通道: y0, y1

普通卷积的group就是1

连接关系是

1
2
3
          x0   x1   x2   x3
y0        ✓    ✓    ✓    ✓
y1        ✓    ✓    ✓    ✓

普通卷积的 kernel shape 是

1
(out_c, in_c, k_h, k_w)

Group 卷积：每个输出通道只看本组输入通道

还是 in_c = 4 out_c = 2，设置groups = 2

输入通道分成 2 组

1
2
Group 0 输入通道: x0, x1
Group 1 输入通道: x2, x3
1
2
3
          x0   x1   x2   x3
y0        ✓    ✓
y1                  ✓    ✓
1
2
3
4
5
6
7
Group 0:
    输入 x0, x1
    输出 y0

Group 1:
    输入 x2, x3
    输出 y1

最后把所有 group 的输出通道拼起来

注意，始终保持kernel_c的大小和实际进来的数据通道数相同，这里kernel_c = in_c//group

如果不相等，就会出现二者不能逐元素相乘的情况

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import numpy as np

def error():
    print("-1")
    print("-1")


def main():
    img = np.array(list(map(int, input().split())), dtype= int)
    batch_size, in_c, img_h, img_w = map(int, input().split())
    kernel = np.array(list(map(int, input().split())), dtype= int)
    out_c, k_c, k_h, k_w = map(int, input().split())

    group = int(input())

    # 分组卷积要求：
    # 输入通道数 in_c 必须能被 group 整除；
    # 输出通道数 out_c 也必须能被 group 整除
    if in_c%group or out_c%group:
        error()
        return
    # 每个 group 内的输入通道数是 in_c // group
    # 卷积核的第二维 k_c 必须等于每组输入通道数
    if in_c // group != k_c:
        error()
        return

    img = img.reshape((batch_size, in_c, img_h, img_w))
    kernel = kernel.reshape((out_c, k_c, k_h, k_w))
    # 无 padding，stride = 1
    out_h, out_w = img_h - k_h +1, img_w - k_w +1
    out = np.zeros((batch_size, out_c, out_h, out_w), dtype = int)

    in_c_group = in_c//group
    out_c_group = out_c//group
    for batch in range(batch_size):
        for g in range(group):
            in_c_start = in_c_group*g
            in_c_end = in_c_group*(g + 1)
            out_c_start = out_c_group*g
            out_c_end = out_c_group*(g + 1)
            # 取当前 batch、当前 group 的输入
            img_group = img[batch, in_c_start:in_c_end, :, :]
            # 取当前 group 对应的卷积核
            kernel_group = kernel[out_c_start:out_c_end, :, :,:]
            # kernel 的 1维度和img的group后的1维度相同
            # in_c // group != k_c 这里已经验证
            # 遍历当前 group 内的输出通道
            for oc in range(out_c_group):
                for i in range(out_h):
                    for j in range(out_w):
                        window = img_group[:, i:i+k_h, j:j+k_w]
                        # window.shape == (in_c_group, k_h, k_w)
                        # kernel_group[oc].shape == (in_c_group, k_h, k_w)
                        # 相乘后仍是 (in_c_group, k_h, k_w)
                        out[batch, out_c_start+oc, i, j] = np.sum(window * kernel_group[oc])

    out_data = out.reshape(-1).tolist()
    out_shape = [batch_size, out_c, out_h, out_w]

    print(" ".join(map(str, out_data)))
    print(" ".join(map(str, out_shape)))


if __name__ == "__main__":
    main()

P4482.第3题-带Padding的卷积计算

第3题-带Padding的卷积计算 - problem_ide - CodeFun2000

pad函数

1
2
3
4
5
6
pad_img = np.pad(
    img_group,
    pad_width=((0, 0), (pad, pad), (pad, pad)), # 对应3维(C,H,W)，pad H和W 
    mode="constant",
    constant_values=0
)
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
import sys
import numpy as np

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    m = int(next(it))
    n = int(next(it))
    kernel = np.array([[int(next(it)) for _ in range(m)] for _ in range(m)])
    img = np.array([[int(next(it)) for _ in range(n)] for _ in range(n)])

    pad = m // 2
    # 扩0
    img_pad = np.pad(
        img,
        ((pad, pad), (pad, pad)),
        mode='constant',
        constant_values=0
    )
    res = np.zeros_like(img)
    for i in range(n):
        for j in range(n):
            window = img_pad[i:i+m, j:j+m]
            res[i][j] = np.sum(window * kernel)
    
    for row in res:
        print(" ".join(map(str, row)))

if __name__ == '__main__':
    main()

逻辑回归

二分类 logistic regression

对于二分类任务，标签只有两类：
$$
y_i\in{0,1}
$$
设：
$$
X\in\mathbb{R}^{N\times d},\quad
w\in\mathbb{R}^{d\times 1},\quad
b\in\mathbb{R},\quad
y\in\mathbb{R}^{N\times 1}
$$

前向传播：单样本形式
$$
z_i=X_iw+b
$$
预测概率为(表示样本 i 属于正类 1 的概率)：
$$
p_i=\hat y_i=\sigma(z_i)=\frac{1}{1+e^{-z_i}}\qquad p_i=P(y_i=1\mid X_i)
$$
batch 形式
$$
z=Xw+b,\quad p=\sigma(z)
$$
对于单个样本，二分类交叉熵为
$$
L_i=-\left[y_i\log p_i+(1-y_i)\log(1-p_i)\right]
$$
Sigmoid 函数为：
$$
\sigma(z)=\frac{1}{1+e^{-z}}
$$
其导数为：
$$
\frac{\partial \sigma(z)}{\partial z}=\sigma(z)(1-\sigma(z))
$$
因为$p_i = \sigma(z)$，所以
$$
\frac{\partial p_i}{\partial z_i}=p_i(1-p_i)
$$
先对$p_i$求导
$$
\frac{\partial L_i}{\partial p_i} =
-\left[
\frac{y_i}{p_i} -
\frac{1-y_i}{1-p_i}
\right]
$$
根据链式法则，并且代入得到
$$
\frac{\partial L_i}{\partial z_i} =
\frac{\partial L_i}{\partial p_i}
\frac{\partial p_i}{\partial z_i}=
\frac{p_i-y_i}{p_i(1-p_i)}
\cdot
p_i(1-p_i)=
p_i-y_i
$$
所以二分类 sigmoid + BCE 有一个重要结论
$$
\color{red} \frac{\partial L_i}{\partial z_i}=p_i-y_i
$$
对参数 w 和 b 求导
$$
\frac{\partial z_i}{\partial w}=X_i^\top,\quad
\frac{\partial z_i}{\partial b}=1
$$

注意，这里默认$X_i\in\mathbb{R}^{1\times d}$，在代码中是(d,)

根据链式法则
$$
\frac{\partial L_i}{\partial w}= X_i^\top(p_i-y_i) \qquad \frac{\partial L_i}{\partial b}

p_i-y_i
$$
Batch Loss
$$
\frac{\partial J}{\partial w} = \frac{1}{N}X^\top(p-y) \qquad \frac{\partial J}{\partial b}

\frac{1}{N}\mathbf{1}^\top(p-y)

\frac{1}{N}\sum_{i=1}^{N}(p_i-y_i)
$$
通常只对 w 正则化，不对 b 正则化
$$
w \leftarrow w - \alpha(\hat y-y)x\\
b \leftarrow b - \alpha(\hat y-y)
$$
正则项梯度为
$$
\frac{\partial}{\partial w}
\frac{\lambda}{2N}|w|2^2 =
\frac{\lambda}{N}w
$$
不加正则时
$$
w\leftarrow w-\eta\frac{1}{N}X^\top(p-y)\qquad b\leftarrow b-\eta\frac{1}{N}\sum{i=1}^{N}(p_i-y_i)
$$
加正则时
$$
w
\leftarrow
w-\eta
\left[
\frac{1}{N}X^\top(p-y)
+
\frac{\lambda}{N}w
\right]
$$
从形式上，softmax的和sigmoid的梯度更新形式相同

代码模板

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def standardize(train_x, test_x, eps=1e-8):
    """
    用训练集统计量标准化 train_x 和 test_x
    注意：mean/std 只能从 train_x 计算，不能从 test_x 计算，否则会数据泄漏
    """
    mean = np.mean(train_x, axis=0, keepdims=True)
    std = np.std(train_x, axis=0, keepdims=True, ddof=0)
    std = np.where(std < eps, 1.0, std)

    train_x_std = (train_x - mean) / std
    test_x_std = (test_x - mean) / std

    return train_x_std, test_x_std

def cross_entropy(p, y):
    return -np.mean(
        y * np.log(p + 1e-12) +
        (1 - y) * np.log(1 - p + 1e-12)
    )
    
def sigmoid(z):
    """
    数值稳定版 sigmoid
    """
    z = np.clip(z, -500, 500)
    return 1.0 / (1.0 + np.exp(-z))

def train_binary_sigmoid(
    train_x,
    train_y,
    learning_rate=0.1,
    lam=1e-4,
    epochs=600,
):
    """
    二分类 Logistic Regression:
        z = Xw + b
        p = sigmoid(z)

    Loss:
        J = BCE + lambda/(2N) * ||w||_2^2

    梯度:
        grad_w = X^T(p-y)/N + lambda/N * w
        grad_b = mean(p-y)
    """
    
    N, D = train_x.shape
    
    X = train_x.astype(np.float64)
    y = train_y.astype(np.float64).reshape(-1)
    
    lr = learning_rate
    W = np.zeros(D, dtype=np.float64)
    b = 0.0
    
    for epoch in range(epochs):
        # 前向传播
        z = X @ W + b       # shape: (N,)
        p = sigmoid(z)      # shape: (N,)

        # 梯度
        delta = p - y         # shape: (N,)
        grad_W = X.T @ delta / N + (lam / N) * W  # shape: (D,)
        grad_b = np.mean(delta)     # scalar

        # 参数更新
        W -= lr * grad_W
        b -= lr * grad_b

    return W, b

def predict(test_x, W, b):
    logits = test_x @ W + b
    prob = softmax(logits)
    return np.argmax(prob, axis=1)

P3872.第3题-基于逻辑回归的意图分类器

第3题-基于逻辑回归的意图分类器 - problem_ide - CodeFun2000

注意one-hot编码，feat的定义

SGD 随机梯度下降，batch为1，所以需要在循环里嵌套一个单样本更新，比较少见，大部分情况下还是一个batch更新一次

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import sys
import numpy as np

def one_hot(s):
    x = np.zeros(7, dtype=np.float64)
    for ch in s:
        idx = ord(ch)-ord('A')
        if 0<= idx < 7:
            x[idx] = 1.0
    return x

def sigmoid(z):
    # 防止 exp 溢出
    z = np.clip(z, -500, 500)
    return 1.0 / (1.0 + np.exp(-z))

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    X = []
    y = []
    for i in range(N):
        feat = one_hot(next(it))
        X.append(feat)
        y.append(float(next(it)))

    X = np.array(X, dtype=np.float64)
    y = np.array(y, dtype=np.float64)

    X_test = []

    for _ in range(M):
        feat = one_hot(next(it))
        X_test.append(feat)

    X_test = np.array(X_test, dtype=np.float64)

    w = np.zeros(7, dtype=np.float64)
    b = 0.0

    alpha = 0.1
    max_iter = 20

    for _ in range(max_iter):
        for i in range(N):
            x_i = X[i]
            y_i = y[i]

            z = x_i @ w + b
            p = sigmoid(z)

            delta = p - y_i

            w -= alpha * delta * x_i
            b -= alpha * delta

    probs = sigmoid(X_test @ w + b)

    for p in probs:
        label = 1 if p > 0.5 else 0
        print(label)

if __name__ == '__main__':
    main()

P4344.第3题-商品购买预测

第3题-商品购买预测 - problem_ide - CodeFun2000

全样本作为一个batch

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
53
54
55
56
57
58
59
60
61
62
import numpy as np

def sigmoid(z):
    z = np.clip(z, -500, 500)
    return 1.0/(1.0+np.exp(-z))

def cross_entropy(p, y):
    return -np.mean(
        y * np.log(p + 1e-12) +
        (1 - y) * np.log(1 - p + 1e-12)
    )
def main():
    data = input().split()
    n = int(data[0])
    max_iter = int(data[1])
    lr = float(data[2])
    lam = float(data[3])
    tol = float(data[4])
    x = []
    y = []
    for _ in range(n):
        data = input().split()
        x.append(data[:-1])
        y.append(data[-1])
    x = np.array(x, dtype=np.float64)
    y = np.array(y, dtype=np.float64)

    n, D = x.shape
    W = np.zeros(D, dtype=np.float64)
    b = 0.0
    prev_loss = None
    for _  in range(max_iter):
        z = x @ W + b
        p = sigmoid(z)
        ce_loss = cross_entropy(p, y)
        l2_loss = lam/(2*n) *np.sum(W*W)
        loss = ce_loss + l2_loss
        if prev_loss is not None and abs(loss- prev_loss)< tol:
            break
        prev_loss = loss
        delta = p - y
        g_W = x.T @ delta / n + lam * W/ n
        g_b = np.mean(delta)

        W -= lr * g_W
        b -= lr * g_b
    # print(W, b)
    # print(x, y)
    m = int(input())
    x_test = []
    for _ in range(m):
        x_test.append(input().split())
    x_test = np.array(x_test, dtype=np.float64)

    for feat in x_test:
        z = feat @ W + b
        p = sigmoid(z)
        pred = 1 if p>=0.5 else 0
        print(f"{pred} {p:.4f}")

if __name__ == "__main__":
    main()

P4905.第2题-5G基站设备故障风险预警

第2题-5G基站设备故障风险预警 - problem_ide - CodeFun2000

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
import numpy as np

def sigmoid(z):
    z = np.clip(z, -500, 500)
    return 1.0/(1.0+np.exp(-z))

def main():
    data = input().split()
    N = int(data[0])
    iter = int(data[1])
    lr = float(data[2])
    x1 = []
    x2 = []
    y = []
    for _ in range(N):
        data = input().split()
        x1.append(float(data[0]))
        x2.append(float(data[1]))
        y.append(float(data[2]))
    x1 = np.array(x1, dtype=np.float64).reshape((N,1))
    x2 = np.array(x2, dtype=np.float64).reshape((N,1))
    y = np.array(y, dtype=np.float64)

    w1 = np.zeros(1)
    w2 = np.zeros(1)
    b = 0.0
    for _ in range(iter):
        z = x1 @ w1 + x2 @ w2 + b
        p = sigmoid(z)

        delta = p - y
        dw1 = x1.T @ delta /N
        dw2 = x2.T @ delta /N
        db = np.mean(delta, axis=0)

        w1 -= lr*dw1
        w2 -= lr*dw2
        b -= lr*db

    data = list(map(float, input().split()))
    feat1 = np.array(data[0], dtype=np.float64).reshape((1,1))
    feat2 = np.array(data[1], dtype=np.float64).reshape((1,1))

    z = feat1 @ w1 + feat2 @ w2 + b
    pred = sigmoid(z)

    print(f"{pred[0]:.4f}")

if __name__ == "__main__":
    main()

决策树

决策树可以理解成一串自动生成的 if-else 判断规则

每次选择一个特征和一个阈值，把样本分成更“纯”的两部分，不断重复，直到叶子节点足够纯，最后用叶子节点中的多数类别作为预测结果

根据决策规则来判断往左还是往右，或者说是直接输出

P3492.第1题-基于决策树预判资源调配优先级

第1题-基于决策树预判资源调配优先级 - problem_ide - CodeFun2000

理解定义，把node类写出来，然后按顺序遍历就行

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
class Node:
    def __init__(self, feature_index, threshold, left, right, label):
        self.feature_index = feature_index
        self.threshold = threshold
        self.left = left
        self.right = right
        self.label = label

def main():
    f, m, n = map(int, input().split())
    tree = []
    for _ in range(m):
        feature_index, threshold, left, right, label = input().split()
        tree.append(Node(int(feature_index), float(threshold), int(left), int(right), int(label)))
    
    for _ in range(n):
        feat = list(map(float, input().split()))
        current = 0 # 从根节点开始
        while True:
            node = tree[current]
            if node.feature_index == -1:
                print(node.label)
                break
            if feat[node.feature_index] <= node.threshold:
                current = node.left
            else:
                current = node.right

if __name__ == '__main__':
    main()

P4969.第2题-随机森林交易风控算法

第2题-随机森林交易风控算法 - problem_ide - CodeFun2000

注意给的输入的idx, left, right是否从0开始，如果下标方便，可以在创建树的时候减1

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
53
54
55
class TreeNode:
    def __init__(self, idx = None, val = None, left = None, right = None, label = None):
        self.idx = idx
        self.val = val
        self.left = left
        self.right = right
        self.label = label

def decision(feat, tree):
    out = []
    for single_tree in tree:
        node = single_tree[0]
        while True:
            if node.val is None:
                out.append(node.label)
                break
            elif feat[node.idx] <= node.val:
                node = single_tree[node.left]
            else:
                node = single_tree[node.right]
    return out

def main():
    T, M, N = map(int, input().split())
    tree = []
    for _ in range(T):
        single_tree = []
        K = int(input())
        for _ in range(K):
            node_data = list(map(int, input().split()))
            if node_data[0] == 1:
                single_tree.append(
                    TreeNode(
                        idx = node_data[1]-1,
                        val = node_data[2],
                        left = node_data[3]-1,
                        right = node_data[4]-1
                    )
                )
            elif node_data[0] == 0:
                single_tree.append(
                    TreeNode(label=node_data[1])
                )
        tree.append(single_tree)

    for _ in range(N):
        feat = list(map(int, input().split()))
        out = decision(feat, tree)
        pre_1 = out.count(1)
        pre_0 = out.count(0)
        print("0") if pre_0 >= pre_1 else print("1")

if __name__ == "__main__":
    main()

P3480.第3题-F1值最优的决策树剪枝

第3题-F1值最优的决策树剪枝 - problem_ide - CodeFun2000

  • 碰到混淆矩阵可以转numpy来做
  • 注意index的取值，从0还是1开始
  • 剪枝递归按每个node走一遍就行了
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import numpy as np
class TreeNode:
    def __init__(self, left, right, idx, val, label):
        self.left = left
        self.right = right
        self.idx = idx
        self.val = val
        self.label = label

def Tree_decision(feat, tree):
    y_pred = []
    for emb in feat:
        node = tree[0]
        while True:
            if node.left == 0:
                y_pred.append(node.label)
                break
            elif emb[node.idx-1] <= node.val:
                node = tree[node.left-1]
            else:
                node = tree[node.right-1]
    return y_pred

def F1_score(y_pred, y_true):
    y_pred = np.asarray(y_pred, dtype=np.float64)
    y_true = np.asarray(y_true, dtype=np.float64)
    tp = np.sum((y_pred == 1) & (y_true == 1))
    fp = np.sum((y_pred == 1) & (y_true == 0))
    fn = np.sum((y_pred == 0) & (y_true == 1))
    if tp == 0:
        f1 = 0
    else:
        f1 = 2*tp/(2*tp + fp + fn)

    return f1

def main():
    N, M, K = map(int, input().split())
    tree = []
    for _ in range(N):
        node_data = list(map(int, input().split()))
        node = TreeNode(
            left = node_data[0],
            right = node_data[1],
            idx = node_data[2],
            val = node_data[3],
            label = node_data[4]
        )
        tree.append(node)

    feat = []
    y_true = []
    for _ in range(M):
        sample_data = list(map(int, input().split()))
        emb = sample_data[:K]
        label = sample_data[-1]
        feat.append(emb)
        y_true.append(label)

    best_f1 = 0.0
    # 枚举每个内部节点，将其临时剪成叶子节点
    for node in tree:
        old_left, old_right = node.left, node.right
        node.left = 0
        node.right = 0

        y_pred = Tree_decision(feat, tree)
        f1 = F1_score(y_pred, y_true)
        best_f1 = max(best_f1, f1)

        node.left, node.right = old_left, old_right

    print(f"{best_f1:.6f}")

if __name__ == "__main__":
    main()

并查集

最重要的是定义class UnionFind

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n
        self.count = n  # 当前连通块数量，可选

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]] # 路径压缩
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        # 按大小合并
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1

P4238.第2题-利用大规模预训练模型实现智能告警聚类与故障诊断

第2题-利用大规模预训练模型实现智能告警聚类与故障诊断 - problem_ide - CodeFun2000

只要知道相似度的定义就好，并且对零向量做额外处理
$$
\mathrm{sim}(i,j) = \frac{v_1\cdot v_2}{||v_1||||v_2||}
$$

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
53
54
55
56
57
import sys
import numpy as np

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.size = [1] * n

    def find(self, x: int) -> int:
        while self.parents[x] != x:
            self.parents[x] = self.parents[self.parents[x]]
            x = self.parents[x]
        return x

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parents[ry] = rx
        self.size[rx] += self.size[ry]

def main():
    data = sys.stdin.readlines()
    n = len(data)
    if n == 0:
        print("0")
        return
    emb = []
    dim = None
    for i in range(n):
        warning_data = data[i].split()
        emb_data = warning_data[1:]
        if dim is None:
            dim = len(emb_data)
        if dim != len(emb_data):
            print("0")
            return
        emb.append(list(map(float, emb_data)))

    emb = np.array(emb, dtype=np.float64)
    uf = UnionFind(n)
    l2 = np.sqrt(np.sum(emb**2, axis= 1))

    for i in range(n):
        for j in range(i+1, n):
            if l2[i] == 0 or l2[j] == 0:
                continue
            sim = np.dot(emb[i], emb[j])/(l2[i]*l2[j])
            if sim>=0.95:
                uf.union(i,j)
    print(max(uf.size))

if __name__ == "__main__":
    main()

P3874.第2题-数据聚类及噪声点识别[重点]

第2题-数据聚类及噪声点识别 - problem_ide - CodeFun2000

DBSCAN 是一种基于密度的聚类算法，不要求你提前指定簇的数量，而是用两个参数判断“哪里足够密集”

参数 含义
eps 邻域半径：两个点距离小于等于这个值，就认为它们是邻居
min_samples 一个点的邻域内至少有多少个点，才算“核心

分为三类点：核心点、边界点、噪声点

对比项 K-means DBSCAN
是否需要指定簇数量 需要指定 k 不需要
是否能发现非球形簇 很弱 可以
是否能识别噪声 不直接支持 支持
对参数敏感吗 对 k 和初值敏感 对 eps 和 min_samples 敏感
适合什么形状 球形、凸形簇 任意形状簇 
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import sys
import numpy as np

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n

    def find(self, x) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx

        self.parent[ry] = rx
        self.size[rx] += self.size[ry]

def main():
    data = input().split()
    eps, min_samples, N = float(data[0]), int(data[1]), int(data[2])

    X = []
    for _ in range(N):
        x = list(map(float, input().split()))
        X.append(x)
    X = np.array(X, dtype=np.float64)

    # 1. 计算所有点两两之间的欧氏距离
    dist = np.linalg.norm(X[:,None,:] - X[None,:,:], axis=2)

    # 2. 统计每个点 eps 邻域内的点数，寻找核心点
    neighbors_count = np.sum(dist < eps, axis=1)
    centers = []
    for i in range(N):
        if neighbors_count[i] >= min_samples:
            centers.append(i)

    if len(centers) == 0:
        print(f"0 {N}")
        return

    # 3. 合并核心点之间的连通关系
    uf = UnionFind(N)
    for a in range(len(centers)):
        for b in range(a + 1, len(centers)):
            i = centers[a]
            j = centers[b]
            if dist[i][j] < eps:
                uf.union(i, j)

    # 4. 给核心点所属连通块分配标签
    labels = np.full(N, -1)
    root_to_label = {}
    next_label = 0
    # 给所有核心点分配簇编号
    for i in range(N):
        if i in centers:
            root = uf.find(i)

            if root not in root_to_label:
                root_to_label[root] = next_label
                next_label+=1
            # 第 i 个点的标签是它root对应的簇标签
            labels[i] = root_to_label[root]
    # 5. 给边界点分配标签
    # 非核心点如果在某个核心点 eps 邻域内，就归到该核心点所在簇
    for i in range(N):
        if i in centers:
            continue
        for j in range(N):
            if j in centers and dist[i][j] < eps:
                labels[i] = labels[j]
                break

    # 6. 统计簇数量和噪声点数量
    cluster_count = next_label
    noise_count = np.sum(labels == -1)

    print(cluster_count, noise_count)
    # # 7. 统计每个簇的数量
    # cluster_size = np.bincount(labels[labels!=-1], minlength=cluster_count)
    # # 输出“簇编号 + 簇大小”
    # order = np.argsort(-cluster_size)
    # 
    # for label in order:
    #     print(label, cluster_size[label])
    
if __name__ == "__main__":
    main()

多写了一个统计和输出，可能会涉及到

P4343.第2题-实体匹配结果合并问题

第2题-实体匹配结果合并问题 - problem_ide - CodeFun2000

几个注意点：

  • set的融合用.update()
  • set的查交集用&

其余流程类似，查完并集以后设置输出

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
53
54
55
56
57
58
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx

        self.parent[ry] = rx
        self.size[rx] += self.size[ry]

def main():
    N = int(input())
    data = []
    for _ in range(N):
        query = input().split()
        data.append(set(query))

    uf = UnionFind(N)
    # 两行结果有公共元素，就属于同一个合并组
    for i in range(N):
        for j in range(i + 1, N):
            if data[i] & data[j]: # 集合交集
                uf.union(i, j)
    # 按并查集根节点合并集合
    merged = {}
    for i in range(N):
        root = uf.find(i)

        if root not in merged:
            merged[root] = set()

        merged[root].update(data[i])
    # 每个合并结果内部按字典序排序
    ans = []
    for group in merged.values():
        ans.append(sorted(group))
    # 合并后的结果列表之间，也按字典序排序
    ans.sort()

    for group in ans:
        print(" ".join(group))

if __name__ == '__main__':
    main()

矩阵

P4538.第2题-基于混淆矩阵，推导分类模型的核心评估指标

第2题-基于混淆矩阵，推导分类模型的核心评估指标 - problem_ide - CodeFun2000

  • 熟悉TP FP FN 的定义

  • 注意为0的情况

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
import numpy as np

def cal_func(y_pred, y_true, weight):
    c = len(weight)
    P = np.zeros_like(weight)
    R = np.zeros_like(weight)
    F1 = np.zeros_like(weight)
    for label in range(c):
        tp = np.sum((y_pred == label) & (y_true == label))
        fp = np.sum((y_pred == label) & (y_true != label))
        fn = np.sum((y_pred != label) & (y_true == label))
        if tp > 0:
            P[label] = tp / (tp+fp)
            R[label] = tp / (tp+fn)
            F1[label] = 2*tp/(2*tp+fp+fn)
    w_P = np.sum(weight * P, axis=0)
    w_R = np.sum(weight * R, axis=0)
    w_F1 = np.sum(weight * F1, axis=0)

    return w_P, w_R, w_F1

def main():
    y_pred = np.array(list(map(int, input().split())), dtype=int)
    y_true = np.array(list(map(int, input().split())), dtype=int)
    weight = np.array(list(map(float, input().split())), dtype=np.float64)

    w_P, w_R, w_F1 = cal_func(y_pred, y_true, weight)

    print(f"{w_P:.2f} {w_R:.2f} {w_F1:.2f}")

if __name__ == "__main__":
    main()

线性回归

在最小二乘法有解析解的情况下使用

读入训练样本 → 构造设计矩阵 X → 用最小二乘求参数 W → 对新样本补截距项 → X_pred @ W 预测 → 按题意取整输出

1
W = np.linalg.lstsq(X, Y, rcond=None)[0]

$$
\hat{Y} = XW
$$

假设每个样本有 3 个特征，线性回归可以写成
$$
\hat{y} = w_0 + w_1x_1 + w_2x_2 + w_3x_3
$$
所以一条训练数据：[x1 x2 x3 price] -> [1.0, x1, x2, x3]

训练数据一般不可能完全满足$XW = Y$

所以线性回归求的是最小化平方误差
$$
\min_W |XW - Y|_2^2
$$
如果要用np.linalg.solve需要先通过正规方程转成方阵
$$
X^\top X W = X^\top Y
$$
然后写：

1
W = np.linalg.solve(X.T @ X, X.T @ Y)

如果是非线性，在构建的时候需要注意输入的构建

比如一个二阶多项式
$$
\hat y = w_0 + w_1x+w_2x^2
$$
这里一条训练数据就是：[x] -> [1.0 x x**2]

注意，这里可以变换格式，不变的就是要对每个地方的数做对应的处理，也就是保证后面输入的X就是对应的x幂次

P4532.第2题-使用线性回归预测手机售价

第2题-使用线性回归预测手机售价 - problem_ide - CodeFun2000

注意四舍五入的写法

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
import sys
import numpy as np
from decimal import Decimal, ROUND_HALF_UP

def round_half_up(x):
    return Decimal(str(x)).quantize(Decimal('1'), rounding=ROUND_HALF_UP)

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    K = int(next(it))
    x = []
    y = []
    for _ in range(K):
        x1 = int(next(it))
        x2 = int(next(it))
        x3 = int(next(it))
        price = int(next(it))
        x.append([1.0, x1, x2, x3])
        y.append(price)

    X = np.array(x, dtype=np.float64)
    Y = np.array(y, dtype=np.float64)

    W = np.linalg.solve(X.T @ X, X.T @ Y)

    N = int(next(it))

    ans = []

    for _ in range(N):
        x1 = int(next(it))
        x2 = int(next(it))
        x3 = int(next(it))

        feat = np.array([1.0, x1, x2, x3], dtype=np.float64)

        pred = feat @ W
        ans.append(round_half_up(pred))

    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    main()

P4572.第3题-动态区间的多项式岭回归

第3题-动态区间的多项式岭回归 - problem_ide - CodeFun2000 40min

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
import numpy as np

def main():
    M, N = map(int, input().split())
    X = []
    Y = []
    miss_idx = []
    for i in range(N):
        data = input()
        if data[0] == "M":
            miss_idx.append(i)
            Y.append(0)
        else:
            Y.append(float(data))
        X.append([1.0, i+1, (i+1)**2])
    X = np.array(X, dtype=np.float64)
    Y = np.array(Y, dtype=np.float64)

    for i in range(M):
        last = miss_idx[i - 1] if i!=0 else -1
        next = miss_idx[i + 1] if i!=M-1 else N
        interval_X = np.concatenate([
            X[last+1:miss_idx[i], :],
            X[miss_idx[i]+1:next, :]
        ])
        interval_Y = np.concatenate([
            Y[last+1:miss_idx[i]],
            Y[miss_idx[i]+1:next]
        ])

        interval_W = np.linalg.solve(
            interval_X.T @ interval_X + 0.1 * np.eye(3),
            interval_X.T @ interval_Y
        )

        Y[miss_idx[i]] = X[miss_idx[i]] @ interval_W

    for i in range(len(miss_idx)):
        print(f"Missing_{i+1}: {Y[miss_idx[i]]:.2f}")

if __name__ == "__main__":
    main()

KNN

一个最小模板

算距离 → 排序取前 K 个 → 取标签 → 投票 → 输出票数最多的标签

1
2
3
4
5
6
7
8
9
10
diff = X - feat[None, :]
dist = np.linalg.norm(diff, axis=1)

neighbors_idx = np.argsort(dist)[:K]
neighbors_label = Y[neighbors_idx]

votes = np.bincount(neighbors_label)
ans = np.argmax(votes)

print(ans)

P3479.第2题-标签样本数量

第2题-标签样本数量 - problem_ide - CodeFun2000

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
import numpy as np

def main():
    k, m, n, s = map(int, input().split())
    feat = np.array(list(map(float, input().split())), dtype=np.float64)
    x = []
    y = []
    for _ in range(m):
        data = list(map(float, input().split()))
        x.append(data[:-1])
        y.append(data[-1])

    x = np.array(x, dtype=np.float64)  # [n,k]
    y = np.array(y, dtype=int)

    dist = np.linalg.norm(x - feat, axis=1)
    neighbors = np.argsort(dist)[:k]
    neighbors_label = y[neighbors]
    votes = np.bincount(neighbors_label, minlength=s)
    label = np.argmax(votes)
    print(f"{label} {votes[label]}")


if __name__ == "__main__":
    main()

基于KNN的语音数据分类

第3题-基于KNN的语音数据分类 - problem_ide - CodeFun2000

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
import numpy as np

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    for _ in range(N):
        data = list(map(float, input().split()))
        X.append(data[:-1])
        Y.append(data[-1])
    X = np.array(X, dtype=np.float64)
    Y = np.array(Y, dtype=int)
    feat = np.array(list(map(float, input().split())), dtype=np.float64)

    # KNN
    dist = np.linalg.norm((X-feat), axis= 1)
    neighbors = np.argsort(dist)[:K]
    neighbors_label = Y[neighbors]
    
    # # 投票排序
    # neighbors_dist = dist[neighbors]
    # votes = {}
    # for lab, d in zip(neighbors_label, neighbors_dist):
    #     if lab not in votes:
    #         votes[lab] = [0, d]
    #     votes[lab][0] +=1
    #     votes[lab][1] = min(votes[lab][1], d)
    # ans = sorted(
    #     votes.items(),
    #     key = lambda x : (-x[1][0], x[1][1], x[0])
    # )[0][0]
    
    # 简单做就直接排序
    votes = np.bincount(neighbors_label)
    ans = np.argmax(votes)
    print(ans)

if __name__ == '__main__':
    main()

双指针

P4547.第2题-基于样本纯净度指标的大模型训练数据清洗方法

第2题-基于样本纯净度指标的大模型训练数据清洗方法 - problem_ide - CodeFun2000

就是最长无重复子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def main():
    s = input()
    n = len(s)
    window = set()
    left = ans = 0
    for right in range(n):
        while s[right] in window:
            window.remove(s[left])
            left+=1
        window.add(s[right])
        ans = max(ans, right - left+1)
    print(ans)

if __name__ == "__main__":
    main()

二叉树

1
2
3
4
5
6
# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

建树时有两种输入和输出，一种是紧凑的，一种是非紧凑的

完全二叉树数组下标建树

用固定下标关系建树
$$
left = 2i + 1,\quad right = 2i + 2
$$
比如[1, None, 2, None, None, 3, 4]

建树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def build_full_tree(arr):
    """
    按全 null 站位数组建树：
    左孩子下标 = 2*i+1
    右孩子下标 = 2*i+2
    """
    def dfs(i):
        if i >= len(arr) or arr[i] is None:
            return None

        node = TreeNode(arr[i])
        node.left = dfs(2 * i + 1)
        node.right = dfs(2 * i + 2)

        return node

    return dfs(0)

输出数组：

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
def arr_full_tree(root):
    """
    输出带全 None 站位的数组
    """
    if root is None:
        return []

    val = {}
    q = deque([(root, 0)])
    max_idx = 0

    while q:
        node, idx = q.popleft()

        if node is None:
            continue

        val[idx] = node.val
        max_idx = max(max_idx, idx)
        # 只展开真实节点
        q.append((node.left, 2 * idx + 1))
        q.append((node.right, 2 * idx + 2))

    arr = [val.get(i, None) for i in range(max_idx + 1)]
    return arr

层序遍历数组建树

只给真实节点继续分配左右孩子，None 节点不再展开孩子

建树：

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
def build_tree_compact(arr):
    """
    按不带全 None 的层序数组建树

    例：
    [1, 2, 3, None, 4, None, 5, 6]

    注意：
    None 节点不会继续展开孩子
    """
    if not arr or arr[0] is None:
        return None
    
    root = TreeNode(arr[0])
    q = deque([root])
    idx = 1
    while q:
        node = q.popleft()

        if idx < len(arr) and arr[idx] is not None:
            node.left = TreeNode(arr[idx])
            q.append(node.left)
        idx+=1

        if idx < len(arr) and arr[idx] is not None:
            node.right = TreeNode(arr[idx])
            q.append(node.right)
        idx+=1
    return root

输出数组：

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
def serialize_compact(root):
    """
    输出不带全 None 的层序数组

    会保留中间必要的 None，
    但会删除末尾多余的 None
    """
def arr_compact_tree(root):
    if root is None:
        return []
    arr = []
    q = deque([root])

    while q:
        node = q.popleft()
        if node is None:
            q.append(None)
            continue
        arr.append(node.val)
        q.append(node.left)
        q.append(node.right)
    
    while arr and arr[-1] is None:
        arr.pop()
    
    return arr

格式化输出

把None换为”null”形式，也许需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def format_tree_array(arr):
    """
    把 Python 数组输出成题目常见格式：
    None -> null

    例：
    [1, None, 2] -> "[1,null,2]"
    """
    items = []

    for x in arr:
        if x is None:
            items.append("null")
        else:
            items.append(str(x))

    return "[" + ",".join(items) + "]"

P3657.第2题-二叉树中序遍历的第k个祖先节点

第2题-二叉树中序遍历的第k个祖先节点 - problem_ide - CodeFun2000

两个目标：

  • 获得中序遍历
  • 获得祖先节点

这两件事情可以在一个dfs里实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def dfs(node):
    if node is None:
        return False
    if node.val == find_val:
        return True
    # 目标在左子树：当前节点在 u 的中序后面，不加入
    if dfs(node.left):
        return True
    # 准备搜右子树：如果目标在右子树，当前节点就在 u 前面，可加入 
    path.append(node.val)
    if dfs(node.right):
        return True
    # 右子树没找到，说明当前节点不是目标的相关祖先，撤销
    path.pop()
    return False

然后要知道怎么建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode:
    def __init__(self, val = 0, left = None, right =None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_compact(arr):
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i<len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i+=1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i+=1
    return root

拼起来就是这道题了

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
53
54
55
56
57
58
59
60
61
62
from collections import deque

class TreeNode:
    def __init__(self, val = 0, left = None, right =None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_compact(arr):
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i<len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i+=1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i+=1
    return root

def main():
    tree_data = input().split()
    find_val, k = map(int, input().split())
    tree_arr = []
    for x in tree_data:
        if x == "#":
            tree_arr.append(None)
        else:
            tree_arr.append(int(x))

    tree_root = build_tree_compact(tree_arr)
    path = []

    def dfs(node):
        if node is None:
            return False
        if node.val == find_val:
            return True
        # 目标在左子树：当前节点在 u 的中序后面，不加入 ans
        if dfs(node.left):
            return True
        # 准备搜右子树：如果目标在右子树，当前节点就在 u 前面
        path.append(node.val)
        if dfs(node.right):
            return True
        # 右子树没找到，说明当前节点不是目标的相关祖先，撤销
        path.pop()
        return False

    dfs(tree_root)
    if len(path) < k:
        print("-1")
        return
    print(path[k-1])


if __name__ == "__main__":
    main()

P4476.第3题-Prompt上下文信息精简:找出二叉树中的最大值子树

第3题-Prompt上下文信息精简:找出二叉树中的最大值子树 - problem_ide - CodeFun2000

熟悉建树和输出数组的写法

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from collections import deque

class TreeNode:
    def __init__(self, val = None, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

def is_null(x):
    return x is None or x =="null"

def build_full_null_tree(arr):
    def dfs(i):
        if i >= len(arr) or is_null(arr[i]):
            return None
        node = TreeNode(arr[i])
        node.left = dfs(i*2+1)
        node.right = dfs(i*2+2)
        return node
    return dfs(0)

def arr_full_null_tree(root):
    q = deque([(root, 0)])
    pos = {}
    max_idx = 0
    while q:
        node, idx = q.popleft()
        if node is None:
            continue
        pos[idx] = node.val
        max_idx = max(max_idx, idx)
        q.append((node.left, 2*idx+1))
        q.append((node.right, 2*idx+2))

    return [pos.get(i, None) for i in range(max_idx+1)]

def main():
    data = input()
    if data == "[]":
        print("[]")
        return
    data = data[1:-1]
    tree_list = data.strip().split(',')
    tree_arr = []
    for node_val in tree_list:
        if is_null(node_val):
            tree_arr.append(None)
        else:
            tree_arr.append(int(node_val))

    root = build_full_null_tree(tree_arr)
    best_root = None
    best_sum = float("-inf")
    def dfs(node):
        nonlocal best_root, best_sum
        if node is None:
            return 0
        left_sum = dfs(node.left)
        right_sum = dfs(node.right)
		 # 左子树贡献小于等于 0，剪掉
        if left_sum <= 0:
            node.left = None
        if right_sum <= 0:
            node.right = None

        # 右子树贡献小于等于 0，剪掉
        cur_sum = node.val
        if left_sum > 0:
            cur_sum +=left_sum
        if right_sum > 0:
            cur_sum +=right_sum
        if cur_sum > best_sum:
            best_sum = cur_sum
            best_root = node
        return cur_sum

    dfs(root)
    best_arr = arr_full_null_tree(best_root)
    ans = []

    for x in best_arr:
        if x is None:
            ans.append("null")
        else:
            ans.append(str(x))

    print("[" + ",".join(ans) + "]")

if __name__ == "__main__":
    main()

结构化剪枝

P4518.第2题-基于剪枝的神经网络模型压缩

第2题-基于剪枝的神经网络模型压缩 - problem_ide - CodeFun2000

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
import numpy as np
from decimal import Decimal, ROUND_HALF_DOWN
def round_half_down(x):
    x = Decimal(str(x))
    return int(x.quantize(Decimal('1'), rounding=ROUND_HALF_DOWN))

def pred(h):
    h_norm = h - np.max(h, axis = 1, keepdims=True)
    y_pred = np.exp(h_norm) / np.sum(np.exp(h_norm), axis = 1, keepdims=True)
    label = np.argmax(y_pred, axis=1)
    return label

def main():
    n, d, c = map(int, input().strip().split())

    X = np.array(
        [list(map(float, input().strip().split())) for _ in range(n)],
        dtype=np.float64
    )
    W = np.array(
        [list(map(float, input().strip().split())) for _ in range(d)],
        dtype=np.float64
    )
    ratio = float(input())
    k = round_half_down(d*ratio)
    if ratio>0 and k == 0:
        k = 1
    W_l1 = np.sum(np.abs(W), axis = 1)
    delete_dim = np.argsort(W_l1)[:k]

    W_new = np.delete(W, delete_dim, axis = 0)
    X_new = np.delete(X, delete_dim, axis = 1)

    h = np.dot(X_new, W_new)
    label = pred(h)
    print(" ".join(map(str, label)))

if __name__ == "__main__":
    main()

熟练使用np去操作维度

线性代数

P4277.第2题-人脸关键点对齐

第2题-人脸关键点对齐 - problem_ide - CodeFun2000

仿射变换需要逆变换，正变会出现空洞

矩阵求逆

1
np.linalg.inv(A)

二阶矩阵
$$
A =
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
$$
如果$\det(A) \neq 0$

那么逆矩阵为

$$
A^{-1}
{}={}
\frac{1}{ad - bc}
\begin{bmatrix}
d & -b \\
-c & a
\end{bmatrix}
$$

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
53
54
55
56
57
58
59
60
61
62
63
64
import numpy as np

def print_output(O, row_O):
    flat = O.reshape(-1)
    col_O = len(flat) // row_O

    for r in range(row_O):
        start = r * col_O
        end = start + col_O
        print(" ".join(map(str, flat[start:end])))

def main():
    row_A, row_M, row_O = map(int, input().split())

    A = np.array(
        [list(map(int, input().split())) for _ in range(row_A)],
        dtype=int
    )

    M = np.array(
        [list(map(float, input().split())) for _ in range(row_M)],
        dtype=float
    )

    oh, ow = map(int, input().split())

    Ah, Aw = A.shape

    a, b, tx = M[0]
    c, d, ty = M[1]

    det = a * d - b * c
    O = np.zeros((oh, ow), dtype=int)

    if abs(det) < 1e-12:
        print_output(O, row_O)
        return

    for i in range(oh):
        for j in range(ow):
            # 输出图坐标
            xp = j
            yp = i

            # 去掉平移
            dx = xp - tx
            dy = yp - ty

            # 逆向映射回原图坐标
            x = (d * dx - b * dy) / det
            y = (-c * dx + a * dy) / det

            # 最近邻取整
            src_j = int(np.floor(x + 0.5))
            src_i = int(np.floor(y + 0.5))

            # 判断是否在原图范围内
            if 0 <= src_i < Ah and 0 <= src_j < Aw:
                O[i][j] = A[src_i][src_j]

    print_output(O, row_O)

if __name__ == "__main__":
    main()

P4998.第3题-回归任务反向传播机理

第3题-回归任务反向传播机理 - problem_ide - CodeFun2000

对着题目写就行了，主要是搞明白维度，内积外积

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
53
import numpy as np

def main():
    d_in, d_hidden, d_out = map(int, input().split())
    W_1 = np.array(
        [list(map(float, input().split())) for _ in range(d_hidden)],
        dtype=np.float64
    )
    b_1 = np.array(list(map(float, input().split())), dtype=np.float64)
    W_2 = np.array(
        [list(map(float, input().split())) for _ in range(d_out)],
        dtype=np.float64
    )
    b_2 = np.array(list(map(float, input().split())), dtype=np.float64)
    x = np.array(list(map(float, input().split())), dtype=np.float64)
    y = np.array(list(map(float, input().split())), dtype=np.float64)
    eta = float(input())

    z_1 = x @ W_1.T + b_1
    alpha_1 = np.maximum(z_1, 0)

    y_pred = alpha_1 @ W_2.T + b_2

    delta_2 = y_pred - y
    g_W2 = np.outer(delta_2, alpha_1)
    g_b2 = delta_2

    delta_1 = delta_2 @ W_2
    delta_1[z_1 <=0] = 0

    g_W1 = np.outer(delta_1, x)
    g_b1 = delta_1

    # update
    W_1_new = W_1 - eta * g_W1
    b_1_new = b_1 - eta * g_b1
    W_2_new = W_2 - eta * g_W2
    b_2_new = b_2 - eta * g_b2

    # output
    for row in W_1_new:
        print(" ".join(f"{v:.6f}" for v in row))

    print(" ".join(f"{v:.6f}" for v in b_1_new))

    for row in W_2_new:
        print(" ".join(f"{v:.6f}" for v in row))

    print(" ".join(f"{v:.6f}" for v in b_2_new))
    print(" ".join(f"{v:.6f}" for v in y_pred))

if __name__ == "__main__":
    main()

VIT

假设输入图片是：
$$
X \in \mathbb{R}^{B \times C \times H \times W}
$$
ViT 会把图片切成大小为 $P\times P$ 的小块
$$
N = \frac{H}{P} \times \frac{W}{P}
$$
将第 b 张图片中的第 i 个 patch 展平成一个向量，记为：
$$
\mathbf{p}_{b,i} \in \mathbb{R}^{P^2C}
$$
假设图片尺寸是 224×224，patch size 是 16×16，那么 patch 数量是
$$
N = \frac{224}{16} \times \frac{224}{16} = 14 \times 14 = 196
$$
每个 patch 的原始形状是 $C \times P \times P$

如果是 RGB 图像，那么一个 patch 展平成向量后长度是
$$
3 \times 16 \times 16 = 768
$$
然后用一个线性层把它映射到 Transformer 的 embedding 维度 $D$
$$
\mathbf{z}{b,i} = \mathbf{p}{b,i} W_E + \mathbf{b}E
$$
其中
$$
\mathbf{p}{b,i} \in \mathbb{R}^{P^2C},
\quad
W_E \in \mathbb{R}^{P^2C \times D},
\quad
\mathbf{b}E \in \mathbb{R}^{D},
\quad
\mathbf{z}{b,i} \in \mathbb{R}^{D}
$$
所以 Patch Embedding 的本质是：把每个图像小块展平成向量，然后通过一个线性层映射成 Transformer 可以处理的 token embedding

对整个 batch 来说，Patch Embedding 之后得到
$$
Z_p \in \mathbb{R}^{B \times N \times D}
$$
其中$N$是patch的数量

ViT 中还有一个可学习的 CLS token，记为
$$
\mathbf{z}{\text{cls}} \in \mathbb{R}^{1 \times 1 \times D}
$$
训练时它是一个可学习参数，对于 batch 输入，需要把它复制到 batch 维度上
$$
Z{\text{cls}} \in \mathbb{R}^{B \times 1 \times D}
$$
然后把 CLS token 拼接到所有 patch tokens 的最前面
$$
Z = [Z_{\text{cls}}; Z_p] \in \mathbb{R}^{B \times (N+1) \times D}
$$
接着给整个序列加上位置编码，位置编码也是可学习参数，记为：
$$
E_{\text{pos}} \in \mathbb{R}^{1 \times (N+1) \times D}
$$

INT8量化

类型 量化范围 0 是否映射到整数 0 优点 缺点
对称量化 围绕 0 对称 是 计算简单，矩阵乘法方便 对偏移数据可能浪费范围
非对称量化 由 min/max 决定 不一定 更充分利用 int8 范围 计算时要处理 offset / zero point

P4464.第2题-全连接层INT8非对称量化实现

第2题-全连接层INT8非对称量化实现 - problem_ide - CodeFun2000 30min

注意点：

  • 反量化的时候用的scale 和 min(v)是量化时候的，需要把数据存出来
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
from decimal import Decimal, ROUND_HALF_UP

def quant(X):
    max_v = np.max(X)
    min_v = np.min(X)
    if max_v == min_v:
        scale = 0
        X_quant = np.full_like(X, -128)
    else:
        scale = (max_v - min_v)/255
        X_quant = np.round((X-min_v)/scale) - 128
        X_quant[X_quant < -128] = -128
        X_quant[X_quant > 127] = 127

    # print(X_quant)
    return X_quant, scale, min_v
def dequant(X_quant, scale, min_v):
    if scale == 0:
        X_dequant = np.full_like(X_quant, min_v)
    else:
        X_dequant = (X_quant + 128)* scale + min_v
    # print(X_dequant)
    return X_dequant

def main():
    n = int(input())
    x = np.array(list(map(float, input().split())),dtype = np.float64)
    m, _ = map(int, input().split())
    W = np.array([list(map(float, input().split())) for _ in range(m)],dtype = np.float64)

    # print(x)
    # print(W)
    # 原始输出
    Y = x @ W.T
    # print(Y)
    x_quant, scale_x, min_v_x= quant(x)
    W_quant, scale_W, min_v_W = quant(W)
    Y_quant = x_quant @ W_quant.T
    print(" ".join(map(str, Y_quant.astype(np.int64))))

    x_dequant = dequant(x_quant, scale_x, min_v_x)
    W_dequant = dequant(W_quant, scale_W, min_v_W)
    Y_dequant = x_dequant @ W_dequant.T
    MSE = np.mean((Y- Y_dequant)**2) * 100000
    MSE = round(MSE)

    print(MSE)

if __name__ =="__main__":
    main()