华为AI岗--笔试（一）

import math
from collections import deque

def euclidean_distance(p1, p2):
    """计算两点之间的欧氏距离"""
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))


def dbscan(points, eps, min_samples):
    """
    DBSCAN聚类算法
    
    Args:
        points: 数据点列表，每个点是一个坐标元组
        eps: 邻域半径
        min_samples: 核心点的最小邻居数
    
    Returns:
        labels: 每个点的聚类标签，-1表示噪声点
        n_clusters: 簇的数量
        n_noise: 噪声点的数量
    """
    n = len(points)
    labels = [0] * n          # 0: 未访问, -1: 噪声, >0: 簇编号
    cluster_id = 0
    
    def region_query(point_idx):
        """查找点point_idx的eps邻域内所有点的索引"""
        neighbors = []
        for i in range(n):
            if euclidean_distance(points[point_idx], points[i]) <= eps:
                neighbors.append(i)
        return neighbors
    
    def expand_cluster(point_idx, neighbors, cluster_id):
        """从核心点扩展簇"""
        labels[point_idx] = cluster_id
        queue = deque(neighbors)
        
        while queue:
            current = queue.popleft()
            
            if labels[current] == -1:
                # 将噪声点重新分配到当前簇（边界点）
                labels[current] = cluster_id
            elif labels[current] == 0:
                # 未访问的点
                labels[current] = cluster_id
                current_neighbors = region_query(current)
                if len(current_neighbors) >= min_samples:
                    # 当前点也是核心点，将其邻居加入队列继续扩展
                    queue.extend(current_neighbors)
    
    # 主循环
    for i in range(n):
        if labels[i] != 0:
            continue  # 已经访问过
        
        neighbors = region_query(i)
        if len(neighbors) < min_samples:
            labels[i] = -1  # 标记为噪声点
        else:
            cluster_id += 1
            expand_cluster(i, neighbors, cluster_id)
    
    n_clusters = cluster_id
    n_noise = sum(1 for label in labels if label == -1)
    
    return labels, n_clusters, n_noise


def main():
    """解析输入并执行DBSCAN"""
    # 输入格式：
    # 第一行：n eps min_samples
    # 接下来n行：每行的坐标（空格分隔）
    n, eps, min_samples = map(float, input().split())
    n = int(n)
    
    points = []
    for _ in range(n):
        coord = tuple(map(float, input().split()))
        points.append(coord)
    
    labels, n_clusters, n_noise = dbscan(points, eps, min_samples)
    
    print(f"簇的数量：{n_clusters}")
    print(f"噪声点数量：{n_noise}")
    
    # 打印每个点的标签
    for i, label in enumerate(labels):
        if label == -1:
            print(f"点{i}: 噪声")
        else:
            print(f"点{i}: 簇{label}")


if __name__ == "__main__":
    main()

import numpy as np


def softmax(x, axis=-1):
    """
    数值稳定的Softmax函数
    
    Args:
        x: 输入数组
        axis: 沿哪个轴计算softmax
    
    Returns:
        softmax概率分布
    """
    # 减去最大值以防止数值溢出
    x_max = np.max(x, axis=axis, keepdims=True)
    exp_x = np.exp(x - x_max)
    return exp_x / np.sum(exp_x, axis=axis, keepdims=True)


def masked_multi_head_attention(X, W_Q, W_K, W_V, W_O, mask=None):
    """
    Masked Multi-Head Self-Attention
    
    Args:
        X: 输入序列 (batch_size, seq_len, d_model)
        W_Q: Query权重 (num_heads, d_model, d_k)
        W_K: Key权重 (num_heads, d_model, d_k)
        W_V: Value权重 (num_heads, d_model, d_v)
        W_O: Output投影权重 (num_heads * d_v, d_model)
        mask: 注意力掩码 (seq_len, seq_len)，默认使用因果掩码
    
    Returns:
        output: 注意力输出 (batch_size, seq_len, d_model)
    """
    batch_size, seq_len, d_model = X.shape
    num_heads = W_Q.shape[0]
    d_k = W_Q.shape[2]
    d_v = W_V.shape[2]
    
    # 1. 生成因果掩码（Causal Mask / Upper Triangular Mask）
    if mask is None:
        # 下三角矩阵：可以注意到自身及之前的位置
        mask = np.triu(np.ones((seq_len, seq_len)), k=1) * -1e9
        # 0的地方（下三角）可以注意，1的地方（上三角）被mask掉
        # 使用极大的负数作为mask值，这样经过softmax后概率趋近于0
    
    # 2. 计算Q, K, V — 为每个头独立线性变换
    # X: (B, L, D) → Q: (B, H, L, d_k)
    Q = np.zeros((batch_size, num_heads, seq_len, d_k))
    K = np.zeros((batch_size, num_heads, seq_len, d_k))
    V = np.zeros((batch_size, num_heads, seq_len, d_v))
    
    for h in range(num_heads):
        # 每个头使用自己的权重矩阵
        for b in range(batch_size):
            Q[b, h] = X[b] @ W_Q[h]       # (L, d_model) @ (d_model, d_k) → (L, d_k)
            K[b, h] = X[b] @ W_K[h]       # (L, d_model) @ (d_model, d_k) → (L, d_k)
            V[b, h] = X[b] @ W_V[h]       # (L, d_model) @ (d_model, d_v) → (L, d_v)
    
    # 3. 计算Scaled Dot-Product Attention
    # Attention(Q, K, V) = softmax(QK^T / sqrt(d_k) + mask) * V
    scale = np.sqrt(d_k)
    
    # QK^T: (B, H, L, L)
    scores = Q @ K.transpose(0, 1, 3, 2) / scale  # (B, H, L, d_k) @ (B, H, d_k, L) → (B, H, L, L)
    
    # 添加mask：将不应注意的位置设为极小值
    scores = scores + mask  # mask广播到 (B, H, L, L)
    
    # Softmax沿最后一个维度（每个查询对所有键的注意力权重）
    attn_weights = softmax(scores, axis=-1)  # (B, H, L, L)
    
    # 加权求和：attn @ V
    context = attn_weights @ V  # (B, H, L, L) @ (B, H, L, d_v) → (B, H, L, d_v)
    
    # 4. 拼接多头并做输出投影
    # 将 (B, H, L, d_v) reshape 为 (B, L, H * d_v)
    concat = np.zeros((batch_size, seq_len, num_heads * d_v))
    for b in range(batch_size):
        concat[b] = context[b].transpose(1, 0, 2).reshape(seq_len, num_heads * d_v)
    
    # 输出投影: (B, L, H*d_v) @ (H*d_v, d_model) → (B, L, d_model)
    output = concat @ W_O
    
    return output


def main():
    """解析输入并执行Masked Multi-Head Attention"""
    # 输入格式（示例）：
    # 第一行：batch_size seq_len d_model num_heads d_k d_v
    # 然后是X矩阵，然后是W_Q, W_K, W_V, W_O矩阵
    
    data = input().strip().split()
    batch_size = int(data[0])
    seq_len = int(data[1])
    d_model = int(data[2])
    num_heads = int(data[3])
    d_k = int(data[4])
    d_v = int(data[5])
    
    # 读取输入矩阵（简化起见，此处用随机数据演示）
    # 实际笔试中会按照给定格式逐行读取
    np.random.seed(42)
    X = np.random.randn(batch_size, seq_len, d_model)
    W_Q = np.random.randn(num_heads, d_model, d_k)
    W_K = np.random.randn(num_heads, d_model, d_k)
    W_V = np.random.randn(num_heads, d_model, d_v)
    W_O = np.random.randn(num_heads * d_v, d_model)
    
    output = masked_multi_head_attention(X, W_Q, W_K, W_V, W_O)
    print(f"输出形状：{output.shape}")  # (batch_size, seq_len, d_model)
    print("前3个位置的输出值：")
    print(output[0, :3, :3])


if __name__ == "__main__":
    main()

n = int(input())

a, b, c = map(int, input().split())

lines = []
while True:
    try:
        line = input().strip()
        if not line:
            break
        lines.append(line)
    except EOFError:
        break

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

# 输入：[[1,2],[3,4],[5,6]]
arr = eval(input())  # 直接将字符串解析为Python列表

# 保留两位小数
print(f"{value:.2f}")
# 或
print("{:.2f}".format(value))