华为 AI 机考必刷 35 题：Python 注释解法 ¶

import sys


def minimum_cost(n, budget, forward_time, memory):
    # prefix[i]：前 i 层的前向耗时之和。
    # weighted[i]：前 i 层的「层号 × 耗时」之和。
    prefix = [0] * (n + 1)
    weighted = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + forward_time[i - 1]
        weighted[i] = weighted[i - 1] + i * forward_time[i - 1]

    # cost[c][d]：相邻检查点 c、d 之间的重计算代价。
    # 把 sum(f[k-1] * (d-k)) 拆成两项，用前缀和 O(1) 求出。
    cost = [[0] * (n + 1) for _ in range(n + 1)]
    for d in range(1, n + 1):
        for c in range(d):
            time_sum = prefix[d - 1] - prefix[c]
            weighted_sum = weighted[d - 1] - weighted[c]
            cost[c][d] = d * time_sum - weighted_sum

    # dp[d][w]：以 d 为最后一个检查点，使用至多 w 显存的最小代价。
    # 第 0 层是免费起点；无论预算是多少，起点的代价均为 0。
    inf = float('inf')
    dp = [[inf] * (budget + 1) for _ in range(n + 1)]
    dp[0] = [0] * (budget + 1)

    for d in range(1, n + 1):
        # 最后一层是免费终点，不需要为它保存检查点。
        need = 0 if d == n else memory[d - 1]
        if need > budget:
            continue
        current = dp[d]
        for c in range(d):
            previous = dp[c]
            interval_cost = cost[c][d]
            for w in range(need, budget + 1):
                candidate = previous[w - need] + interval_cost
                if candidate < current[w]:
                    current[w] = candidate

    return dp[n][budget]


def main():
    # sys.stdin.buffer.read() 一次读入标准输入；split() 按空白分割。
    # map(int, ...) 把字符串逐个转换成整数；list(...) 保存为列表。
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n, budget = data[0], data[1]
    forward_time = data[2:2 + n]  # 切片左闭右开，恰好取 n 个元素。
    memory = data[2 + n:2 + 2 * n]
    print(minimum_cost(n, budget, forward_time, memory))


if __name__ == '__main__':
    # 直接运行文件时执行 main；被测试程序导入时不会自动读取输入。
    main()

5 3
5 10 5 10 20
1 2 1 3 1

15

import sys


def minimum_cost(required, sizes, swap_costs, recompute_costs):
    # 总空间都不够时，无论怎样选择都没有解。
    if sum(sizes) < required:
        return None

    # dp[s]：释放 s 空间的最小代价。
    # s == required 表示「已经释放至少 required 空间」。
    # 超过需求的空间都合并进这个状态，避免数组过大。
    inf = float('inf')
    dp = [inf] * (required + 1)
    dp[0] = 0
    reachable = 0  # 当前已经处理的张量最多能释放多少空间。

    # zip 把三个列表按位置配对，每次循环取出一个张量的信息。
    for size, swap_cost, recompute_cost in zip(sizes, swap_costs, recompute_costs):
        # 两种操作释放相同的空间，只需保留较便宜的一种。
        cost = min(swap_cost, recompute_cost)
        # 倒序遍历是 0/1 背包的关键：每个张量只能选择一次。
        # required 状态已经完成目标，继续加正代价不会更优，所以跳过。
        for space in range(min(reachable, required - 1), -1, -1):
            if dp[space] == inf:
                continue  # 尚不可达的状态不能参与转移。
            next_space = min(required, space + size)
            candidate = dp[space] + cost
            if candidate < dp[next_space]:
                dp[next_space] = candidate
        reachable = min(required, reachable + size)

    return dp[required]


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    required, n = data[0], data[1]
    sizes = data[2:2 + n]
    swap_costs = data[2 + n:2 + 2 * n]
    recompute_costs = data[2 + 2 * n:2 + 3 * n]
    answer = minimum_cost(required, sizes, swap_costs, recompute_costs)
    print('error' if answer is None else answer)


if __name__ == '__main__':
    main()

10
5
3 4 5 6 7
1 2 3 5 5
2 3 4 5 6

6

import sys


def main():
    text = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    scores = {}
    for _ in range(n):
        word, score = sys.stdin.readline().split()
        scores[word] = int(score)
    m = int(sys.stdin.readline())
    transitions = {}
    for _ in range(m):
        first, second, score = sys.stdin.readline().split()
        transitions[first, second] = int(score)

    # dp[i] 是字典：切完前 i 个字符后，最后一个词 -> 最高分。
    # 只记位置不够，因为下一个转移分数还取决于最后一个词。
    dp = [{} for _ in range(len(text) + 1)]
    dp[0][None] = 0  # None 代表还没有第一个词。
    for end in range(1, len(text) + 1):
        for word, score in scores.items():
            start = end - len(word)
            if start < 0 or text[start:end] != word:
                continue
            for previous_word, previous_score in dp[start].items():
                extra = transitions.get((previous_word, word), 0)
                candidate = previous_score + score + extra
                if word not in dp[end] or candidate > dp[end][word]:
                    dp[end][word] = candidate
    # 不能完整切分才输出 0；有效切分的最优得分可能是负数。
    print(max(dp[-1].values()) if dp[-1] else 0)


if __name__ == '__main__':
    main()

applepie
2
pen 3
apple 10
2
pen apple 5
pie apple 2

0

import sys
from decimal import Decimal


def main():
    data = iter(sys.stdin.buffer.read().decode().split())
    layers = int(next(data))
    threshold = Decimal(next(data))
    # 用 Decimal 精确表示输入小数，避免 0.1+0.2 比 0.3 略大的问题。
    # 字典表示「累计精度损失 -> 最小内存」。每层必须恰选一个方案。
    dp = {Decimal(0): Decimal(0)}
    for _ in range(layers):
        count = int(next(data))
        options = []
        for _ in range(count):
            next(data)  # 位宽名称只起说明作用，计算用损失和内存。
            loss = Decimal(next(data))
            memory = Decimal(next(data))
            options.append((loss, memory))
        candidates = {}
        for total_loss, total_memory in dp.items():
            for loss, memory in options:
                new_loss = total_loss + loss
                if new_loss > threshold:
                    continue
                new_memory = total_memory + memory
                if new_loss not in candidates or new_memory < candidates[new_loss]:
                    candidates[new_loss] = new_memory
        # 删除被支配状态：损失更多、内存也不少的状态永远不优。
        dp = {}
        best_memory = Decimal('Infinity')
        for loss in sorted(candidates):
            memory = candidates[loss]
            if memory < best_memory:
                dp[loss] = memory
                best_memory = memory
    if not dp:
        # 页面未规定无解输出；这里报错，避免虚构一个评测答案。
        raise ValueError('题面未说明无解输出；给定数据没有可行量化组合')
    print(f'{min(dp.values()):.2f}')


if __name__ == '__main__':
    main()

2 0.5
2 8bit 0.2 100.0 16bit 0.1 200.0
2 8bit 0.3 150.0 16bit 0.15 300.0

250.00

import sys
import numpy as np


def main():
    data = list(map(float, sys.stdin.buffer.read().split()))
    k, m, iterations = map(int, data[:3])
    points = np.array(data[3:], dtype=float).reshape(m, 4)
    centers = points[:k].copy()  # copy 防止修改中心时影响原始样本。
    labels = np.zeros(m, dtype=int)
    for _ in range(iterations):
        # 广播生成 m×k×4 的坐标差；平方后沿特征维求和。
        # 欧氏距离开不开平方不影响谁最近，因此省略 sqrt。
        distance_squared = ((points[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
        labels = distance_squared.argmin(axis=1)
        updated = centers.copy()
        for cluster in range(k):
            members = points[labels == cluster]
            if len(members):
                updated[cluster] = members.mean(axis=0)
        shift = np.linalg.norm(updated - centers, axis=1)
        centers = updated
        if np.all(shift < 1e-8):
            break
    # n=0 时未执行循环：按初始化中心分配一次，作为明确的边界处理。
    if iterations == 0:
        labels = ((points[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2).argmin(axis=1)
    counts = np.bincount(labels, minlength=k)
    print(*sorted(map(int, counts)))


if __name__ == '__main__':
    main()

3 20 1000
0.11 0.79 0.68 0.97
1.0 0.8 0.13 0.33
0.27 0.02 0.5 0.46
0.83 0.29 0.23 0.75
0.97 0.08 0.84 0.55
0.29 0.71 0.17 0.83
0.03 0.6 0.88 0.28
0.24 0.26 0.82 0.03
0.96 0.12 0.82 0.36
0.13 0.12 0.86 0.44
0.23 0.7 0.35 0.06
0.42 0.49 0.67 0.84
0.8 0.49 0.47 0.7
0.68 0.03 0.11 0.07
0.77 0.19 0.95 0.44
0.25 0.12 0.98 0.04
0.7 0.11 0.53 0.3
0.73 0.67 0.46 0.96
0.11 0.31 0.91 0.57
0.43 0.61 0.13 0.1

4 6 10

import sys
import numpy as np


def main():
    values = iter(sys.stdin.buffer.read().split())
    k = int(next(values))
    centers = np.array([[float(next(values)) for _ in range(3)] for _ in range(k)])
    iterations = int(next(values))
    m = int(next(values))
    points = np.array([[float(next(values)) for _ in range(3)] for _ in range(m)])
    for _ in range(iterations):
        squared = ((points[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
        labels = squared.argmin(axis=1)  # 距离相同取编号较小的中心。
        updated = centers.copy()
        for cluster in range(k):
            members = points[labels == cluster]
            if len(members):
                updated[cluster] = members.mean(axis=0)
        centers = updated
        # 题目要求执行给定次数，不在这里提前停止或四舍五入。
    for center in centers:
        print(' '.join(f'{value:.2f}' for value in center))


if __name__ == '__main__':
    main()

3
50 25 30
60 15 60
25 75 90
3
9
50 25 30
30 50 30
60 15 60
25 75 90
10 05 60
26 15 30
32 67.5 90
80 7.5 60
20 100 90

35.33 30.00 30.00
50.00 9.17 60.00
25.67 80.83 90.00

import sys
import numpy as np
from decimal import Decimal, ROUND_HALF_EVEN


def main():
    values = list(map(int, sys.stdin.buffer.read().split()))
    n, k = values[:2]
    points = np.array(values[2:], dtype=float).reshape(n, 2)
    centers = points[:k].copy()
    for _ in range(100):
        squared = ((points[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
        labels = squared.argmin(axis=1)
        updated = centers.copy()
        for cluster in range(k):
            members = points[labels == cluster]
            if len(members):
                updated[cluster] = members.mean(axis=0)
        converged = np.all(np.linalg.norm(updated - centers, axis=1) <= 1e-6)
        centers = updated
        if converged:
            break
    groups = [np.flatnonzero(labels == c) for c in range(k)]
    # 所有样本两两之间的欧氏距离，用于轮廓系数（此处需要开平方）。
    distances = np.linalg.norm(points[:, None, :] - points[None, :, :], axis=2)
    cluster_scores = []
    for cluster, members in enumerate(groups):
        if len(members) == 0:
            continue
        silhouettes = []
        for i in members:
            if len(members) == 1:
                silhouettes.append(1.0)  # 本题明确规定单点簇系数为 1。
                continue
            a = distances[i, members].sum() / (len(members) - 1)
            other_means = [distances[i, g].mean() for c, g in enumerate(groups) if c != cluster and len(g)]
            if not other_means:
                silhouettes.append(0.0)  # k=1 的兜底约定，题面未规定。
                continue
            b = min(other_means)
            silhouettes.append((b - a) / max(a, b) if max(a, b) else 0.0)
        cluster_scores.append((sum(silhouettes) / len(silhouettes), cluster))
    _, worst = min(cluster_scores)  # 相等时取较小的簇编号。
    # 由原始整数坐标精确求平均，用十进制实现 HALF_EVEN。
    members = groups[worst]
    output = []
    for axis in range(2):
        total = sum(int(points[i, axis]) for i in members)
        mean = Decimal(total) / Decimal(len(members))
        output.append(str(mean.quantize(Decimal('0.01'), rounding=ROUND_HALF_EVEN)))
    print(','.join(output))


if __name__ == '__main__':
    main()

4 2
0 0
0 1
1 0
10 10

0.33,0.33

import sys
import math


def encode(text):
    # 这是「字母是否出现」的多热向量，重复字母不累计次数。
    return [1 if letter in text else 0 for letter in 'ABCDEFG']


def sigmoid(z):
    # 分正负计算，避免对很大的正数调用 exp 发生溢出。
    if z >= 0:
        return 1 / (1 + math.exp(-z))
    value = math.exp(z)
    return value / (1 + value)


def main():
    n, m = map(int, sys.stdin.readline().split())
    training = []
    for _ in range(n):
        text, label = sys.stdin.readline().split()
        training.append((encode(text), int(label)))
    weights = [0.0] * 7
    bias = 0.0
    for _ in range(20):
        # batch=1：每看一个样本立即更新，不能改成整批平均梯度。
        for x, label in training:
            prediction = sigmoid(sum(w * v for w, v in zip(weights, x)) + bias)
            error = prediction - label  # sigmoid + 交叉熵的梯度。
            for i in range(7):
                weights[i] -= 0.1 * error * x[i]
            bias -= 0.1 * error
    for _ in range(m):
        x = encode(sys.stdin.readline().strip())
        probability = sigmoid(sum(w * v for w, v in zip(weights, x)) + bias)
        print(1 if probability > 0.5 else 0)


if __name__ == '__main__':
    main()

10 2
CBG 0
AFE 0
FGD 1
BFG 0
BBA 0
BDD 0
BEG 1
EGE 0
CAF 0
DGD 1
DBA
DAD

0
0

import sys


def main():
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, k = next(data), next(data), next(data)
    nodes = [None] + [tuple(next(data) for _ in range(5)) for _ in range(n)]
    samples = [tuple(next(data) for _ in range(k + 1)) for _ in range(m)]
    reached = [[] for _ in range(n + 1)]
    for sample in samples:
        node = 1
        while node:
            reached[node].append(sample)
            left, right, feature, threshold, label = nodes[node]
            if left == 0:
                break
            # 特征编号从 1 开始，所以读取 sample[feature-1]。
            node = left if sample[feature - 1] <= threshold else right

    def solve(node):
        left, right, feature, threshold, label = nodes[node]
        count = len(reached[node])
        positives = sum(sample[-1] for sample in reached[node])
        # 字典：预测为正的样本数 -> 能达到的最大真正例 TP。
        # 选择把当前整棵子树剪掉，所有经过此处的样本使用当前 label。
        result = {count: positives} if label == 1 else {0: 0}
        if left:
            a, b = solve(left), solve(right)
            # 或者保留当前分裂，左右子树各自独立选最好的剪枝。
            for predicted_a, tp_a in a.items():
                for predicted_b, tp_b in b.items():
                    predicted = predicted_a + predicted_b
                    tp = tp_a + tp_b
                    result[predicted] = max(result.get(predicted, -1), tp)
        return result

    real_positives = sum(sample[-1] for sample in samples)
    answer = 0.0
    for predicted, tp in solve(1).items():
        denominator = predicted + real_positives
        if denominator:
            # F1 = 2TP / (2TP+FP+FN) = 2TP / (预测正例数+真实正例数)。
            answer = max(answer, 2 * tp / denominator)
    print(f'{answer:.6f}')


if __name__ == '__main__':
    main()

7 3 2
2 3 1 50 0
4 5 2 50 0
6 7 2 50 1
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
30 60 1
30 30 1
60 30 1

0.800000

import sys


def main():
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)
    kernel = [[next(data) for _ in range(m)] for _ in range(m)]
    image = [[next(data) for _ in range(n)] for _ in range(n)]
    padding = m // 2  # 奇数卷积核两侧各补 m//2 个 0。
    output = []
    for row in range(n):
        current = []
        for col in range(n):
            total = 0
            for kr in range(m):
                source_row = row + kr - padding
                if not 0 <= source_row < n:
                    continue  # 图像以外是补的 0，不必真的开新数组。
                for kc in range(m):
                    source_col = col + kc - padding
                    if 0 <= source_col < n:
                        # 深度学习里的卷积不翻转卷积核，不做像素截断。
                        total += image[source_row][source_col] * kernel[kr][kc]
            current.append(total)
        output.append(' '.join(map(str, current)))
    print('\n'.join(output))


if __name__ == '__main__':
    main()

3 3
1 0 -1
1 0 -1
1 0 -1
1 2 3
4 5 6
7 8 9

-7 -4 7
-15 -6 15
-13 -4 13

import sys


def main():
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    eps, min_points = float(next(data)), int(next(data))
    points = [(float(next(data)), float(next(data))) for _ in range(n)]
    neighbors = [[i] for i in range(n)]  # 本题邻域包含自己。
    for i in range(n):
        for j in range(i + 1, n):
            dx = points[i][0] - points[j][0]
            dy = points[i][1] - points[j][1]
            if dx * dx + dy * dy <= eps * eps:
                neighbors[i].append(j)
                neighbors[j].append(i)
    core = [len(group) >= min_points for group in neighbors]
    parent = list(range(n))

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

    for i in range(n):
        if core[i]:
            for j in neighbors[i]:
                if core[j]:
                    parent[find(i)] = find(j)
    # 一个边界点可能同时邻接多个互不连通的核心簇。
    # 不能把边界点当桥梁把两个核心簇合并！
    memberships = [{find(j) for j in group if core[j]} for group in neighbors]
    answers = []
    for _ in range(m):
        a, b = int(next(data)), int(next(data))
        # 若存在共同核心簇，就是密度相连；噪声点的集合为空。
        answers.append('1' if memberships[a] & memberships[b] else '0')
    print('\n'.join(answers))


if __name__ == '__main__':
    main()

6 4 2.0 3
0.0 0.0
1.2 0.0
0.4 1.0
12.0 0.0
12.5 0.4
6.0 6.0
0 2
0 3
3 4
1 5

1
0
0
0

import sys


def main():
    # 每行一个样本，维数为 2 或 3；保留按行读入以确定维数。
    eps_text, minimum_text, n_text = sys.stdin.readline().split()
    eps, minimum, n = float(eps_text), int(minimum_text), int(n_text)
    points = [list(map(float, sys.stdin.readline().split())) for _ in range(n)]
    neighbors = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            squared = sum((a - b) ** 2 for a, b in zip(points[i], points[j]))
            if squared < eps * eps:  # 本题的半径条件写的是严格小于。
                neighbors[i].append(j)
                if i != j:
                    neighbors[j].append(i)
    # 按标准 DBSCAN：邻域含自身，数量至少 min_samples 时为核心点。
    core = [len(group) >= minimum for group in neighbors]
    parent = list(range(n))

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

    for i in range(n):
        if core[i]:
            for j in neighbors[i]:
                if core[j]:
                    parent[find(i)] = find(j)
    clusters = len({find(i) for i in range(n) if core[i]})
    # 非核心点只要在某核心点的邻域里就是边界点，否则是噪声。
    noise = sum(not any(core[j] for j in group) for group in neighbors)
    print(clusters, noise)


if __name__ == '__main__':
    main()

2 2 10
0 0
3 3
6 6
9 9
12 12
2 6
6 2
9 5
5 9
10 2

0 10

import sys
import numpy as np
from decimal import Decimal, ROUND_HALF_UP


def main():
    data = iter(sys.stdin.buffer.read().split())
    k = int(next(data))
    training = np.array([[float(next(data)) for _ in range(4)] for _ in range(k)])
    n = int(next(data))
    testing = np.array([[float(next(data)) for _ in range(3)] for _ in range(n)])
    # 增加一列 1，把截距 b 也作为一个待学习的参数。
    x = np.column_stack((np.ones(k), training[:, :3]))
    y = training[:, 3]
    # 最小二乘用 lstsq，避免显式求逆放大浮点误差。
    weights, _, _, _ = np.linalg.lstsq(x, y, rcond=None)
    test_x = np.column_stack((np.ones(n), testing))
    prediction = test_x @ weights  # @ 是矩阵乘法。
    # 题面要求四舍五入取整，不能直接 int（会向 0 截断）。
    answer = [int(Decimal(str(value)).quantize(Decimal('1'), rounding=ROUND_HALF_UP)) for value in prediction]
    print(*answer)


if __name__ == '__main__':
    main()

4
30 23 24 1999 55 53 46 2999 68 85 78 3999 113 90 103 4999
1
126 114 143

6009

import sys


def minimum_peak(weights, k):
    def feasible(limit):
        groups, current = 1, 0
        for weight in weights:
            if current + weight > limit:
                groups += 1
                current = weight
            else:
                current += weight
        return groups <= k

    # 峰值不能小于最大单层计算量，也不必大于所有层的总和。
    low, high = max(weights), sum(weights)
    while low < high:
        middle = (low + high) // 2  # // 是整除，返回整数。
        if feasible(middle):
            high = middle  # middle 可行，继续尝试更小的峰值。
        else:
            low = middle + 1
    return low


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    print(minimum_peak(data[1:1 + n], data[1 + n]))


if __name__ == '__main__':
    main()

1
7
1

7

import sys


def longest_unique(text):
    # 输入只有 ASCII 字母和数字，固定大小数组比字典更省内存。
    last = [-1] * 128
    left = 0
    answer = 0
    for right, char in enumerate(text):
        # 如果旧位置仍在窗口中，把左边界跳到旧位置的下一位。
        left = max(left, last[char] + 1)
        last[char] = right
        answer = max(answer, right - left + 1)
    return answer


def main():
    # bytes 迭代时直接得到 ASCII 整数，适合处理千万字符的输入。
    text = sys.stdin.buffer.readline().rstrip(b'\r\n')
    print(longest_unique(text))


if __name__ == '__main__':
    main()

z

1

import sys


def main():
    predicted = list(map(int, sys.stdin.readline().split()))
    truth = list(map(int, sys.stdin.readline().split()))
    weights = list(map(float, sys.stdin.readline().split()))
    n = len(weights)
    tp = [0] * n
    predicted_count = [0] * n
    true_count = [0] * n
    for p, t in zip(predicted, truth):
        predicted_count[p] += 1
        true_count[t] += 1
        if p == t:
            tp[p] += 1
    precision = recall = f1 = 0.0
    for i, weight in enumerate(weights):
        p = tp[i] / predicted_count[i] if predicted_count[i] else 0.0
        r = tp[i] / true_count[i] if true_count[i] else 0.0
        f = 2 * p * r / (p + r) if p + r else 0.0
        precision += weight * p
        recall += weight * r
        f1 += weight * f
    # 加权 F1 是各类 F1 的加权和，不是加权 P、R 的调和平均。
    print(f'{precision:.2f} {recall:.2f} {f1:.2f}')


if __name__ == '__main__':
    main()

0
0
1.0

1.00 1.00 1.00

import sys
from collections import Counter


def main():
    data = iter(sys.stdin.buffer.read().split())
    n, k = int(next(data)), int(next(data))
    training = []
    for i in range(n):
        vector = [float(next(data)) for _ in range(3)]
        label = int(next(data))
        training.append((vector, label))
    target = [float(next(data)) for _ in range(3)]
    distances = []
    for index, (vector, label) in enumerate(training):
        squared = sum((a - b) ** 2 for a, b in zip(vector, target))
        distances.append((squared, index, label))
    distances.sort()  # 距离相同时保留输入顺序。
    counts = Counter(label for _, _, label in distances[:k])
    # 题面没给平票规则；这里明确约定票数相同时取最小类别编号。
    winner = min(counts, key=lambda label: (-counts[label], label))
    print(winner)


if __name__ == '__main__':
    main()

10 3
0.5 0.3 0.4 0
0.6 0.2 0.5 0
0.4 0.3 0.3 0
0.7 0.4 0.6 0
2.1 2.3 2.2 1
2.3 2.2 2.4 1
2.2 2.4 2.3 1
4.5 4.3 4.4 2
4.4 4.5 4.6 2
4.6 4.4 4.5 2
2.2 2.1 2.3

1

import sys
import numpy as np


def main():
    # 本题输入逗号分隔，用 replace 把逗号变为空格，再分割。
    data = iter(sys.stdin.buffer.read().decode().replace(',', ' ').split())
    length, dimension, classes = int(next(data)), int(next(data)), int(next(data))
    learning_rate = float(next(data))
    target = np.array([float(next(data)) for _ in range(classes)])
    x = np.array([float(next(data)) for _ in range(length * dimension)]).reshape(length, dimension)
    w_mlp = np.array([float(next(data)) for _ in range(dimension * dimension)]).reshape(dimension, dimension)
    w_cls = np.array([float(next(data)) for _ in range(dimension * classes)]).reshape(dimension, classes)
    # 两层都是线性层，无偏置、无激活函数；不要自行添加 softmax。
    hidden = x @ w_mlp
    mean_hidden = hidden.mean(axis=0)
    prediction = mean_hidden @ w_cls
    error = prediction - target
    loss = np.mean(error ** 2)
    grad_prediction = 2 * error / classes  # MSE 对输出的导数。
    grad_cls = np.outer(mean_hidden, grad_prediction)
    # 必须用更新前的分类权重计算另一层梯度，最后同时更新。
    grad_mean_hidden = grad_prediction @ w_cls.T
    grad_mlp = np.outer(x.mean(axis=0), grad_mean_hidden)
    new_mlp = w_mlp - learning_rate * grad_mlp
    new_cls = w_cls - learning_rate * grad_cls

    def show(array):
        print(','.join(f'{value:.2f}' for value in np.asarray(array).reshape(-1)))

    show(prediction)
    show([loss])
    show(new_mlp)
    show(new_cls)


if __name__ == '__main__':
    main()

2,2,3,0.1
1.0,0.0,0.0
1.0,2.0,3.0,4.0
1.0,1.0,1.0,1.0
1.0,0.0,0.0,0.0,0.0,0.0

5.00,0.00,0.00
5.33
0.47,1.00,0.20,1.00
-0.33,0.00,0.00,-1.33,0.00,0.00

import sys
from decimal import Decimal, ROUND_FLOOR


def main():
    data = iter(sys.stdin.buffer.read().decode().split())
    n, d, c = int(next(data)), int(next(data)), int(next(data))
    x = [[float(next(data)) for _ in range(d)] for _ in range(n)]
    weights = [[float(next(data)) for _ in range(c)] for _ in range(d)]
    ratio = Decimal(next(data))
    remove_count = int((ratio * d).to_integral_value(rounding=ROUND_FLOOR))
    if ratio > 0 and remove_count == 0:
        remove_count = 1
    # 按每行的 L1 范数排序；范数相同取原始行号较小的。
    order = sorted(range(d), key=lambda i: (sum(abs(v) for v in weights[i]), i))
    removed = set(order[:remove_count])
    kept = [i for i in range(d) if i not in removed]
    predictions = []
    for sample in x:
        logits = [sum(sample[i] * weights[i][j] for i in kept) for j in range(c)]
        # softmax 保持大小顺序，求 argmax 不必真的计算 exp。
        # 删除全部特征时 logits 全是 0，取最小编号 0。
        predictions.append(max(range(c), key=lambda j: logits[j]))
    print(*predictions)


if __name__ == '__main__':
    main()

2 2 2
1 0
0 1
1 -1
-2 3
0

0 1

import sys


def main():
    image_size, patch_size, channels, embedding_dim = map(int, sys.stdin.buffer.read().split())
    patches_per_side = image_size // patch_size  # // 取整，不足一块的边缘不计。
    token_count = patches_per_side ** 2 + 1  # **2 表示平方，+1 是 cls token。
    # 通道数影响展平后的输入长度，但不影响线性映射后的形状。
    print(token_count, embedding_dim)


if __name__ == '__main__':
    main()

1 1 1 8

2 8

import sys
from fractions import Fraction


def quantize(values):
    low, high = min(values), max(values)
    if high == low:
        return [-128] * len(values), [low] * len(values)
    scale = (high - low) / 255
    # Fraction 精确表示十进制输入；round(Fraction) 实现就近取偶。
    # 这可以正确处理恰好为 127.5 等半整数的量化位置。
    quantized = [max(-128, min(127, round((v - low) / scale) - 128)) for v in values]
    restored = [(q + 128) * scale + low for q in quantized]
    return quantized, restored


def main():
    data = iter(sys.stdin.buffer.read().decode().split())
    n = int(next(data))
    x = [Fraction(next(data)) for _ in range(n)]
    m, weight_columns = int(next(data)), int(next(data))
    if weight_columns != n:
        raise ValueError('权重列数必须与输入向量长度一致')
    weights = [[Fraction(next(data)) for _ in range(n)] for _ in range(m)]
    x_quantized, x_restored = quantize(x)
    # 权重必须整张矩阵一起量化，不能逐行单独计算 scale。
    flat_weights = [value for row in weights for value in row]
    w_quantized, w_restored = quantize(flat_weights)
    integer_output = []
    squared_error = Fraction(0)
    for row in range(m):
        begin = row * n
        q_row = w_quantized[begin:begin + n]
        restored_row = w_restored[begin:begin + n]
        # Python 整数不会产生 int8 溢出，累加结果保留完整整数。
        integer_output.append(sum(a * b for a, b in zip(x_quantized, q_row)))
        original_y = sum(a * b for a, b in zip(x, weights[row]))
        restored_y = sum(a * b for a, b in zip(x_restored, restored_row))
        squared_error += (original_y - restored_y) ** 2
    scaled_mse = squared_error / m * 100000
    # 最终 MSE 非负，四舍五入用 floor(value + 1/2)，与量化取偶不同。
    rounded_error = (2 * scaled_mse.numerator + scaled_mse.denominator) // (2 * scaled_mse.denominator)
    print(*integer_output)
    print(rounded_error)


if __name__ == '__main__':
    main()