解题思路

本题的核心是在资源约束下最大化注意力信息总量。问题可以分解为以下几个步骤进行求解：

首先需要对所有特征向量进行RMSNorm归一化处理。对于每个d维特征向量，计算其均方根值，然后将向量的每个分量除以该均方根值。这一步保证了后续注意力得分计算的标准化基础。

接着计算所有位置对之间的注意力得分。对于任意两个位置i和j（其中i<j），使用归一化后的向量进行缩放点积运算，得到注意力得分$A_{ij}$，并计算其平方值$A_{ij}^2$。由于最终目标函数中使用的是平方值，因此可以直接存储平方值以便后续使用。

问题的关键在于构造路径矩阵M。对于每个位置j，需要从前面的所有位置中选择最多$c_j$个位置建立连接。为了最大化目标函数S，应当采用贪心策略：对于每个位置j，将所有前置位置按照$A_{ij}^2$的值从大到小排序，然后选择前$c_j$个最大的值。这样可以保证每个位置获得的注意力信息量最大。

贪心策略的正确性在于：目标函数S是所有激活连接的$A_{ij}^2$之和，每个位置的选择是相互独立的，因此局部最优解（每个位置选择最大的$c_j$个值）必然能导致全局最优解。

最后将计算得到的S乘以100并四舍五入得到整数输出。

代码实现

Python

import numpy as np

def solve(n, d, vectors, capacities):
    # 步骤1：对所有特征向量进行RMSNorm归一化
    normalized = []
    for vec in vectors:
        # 计算均方根值
        rms = np.sqrt(np.mean(np.array(vec) ** 2))
        # 归一化
        normalized.append(np.array(vec) / rms)
    
    # 步骤2：计算注意力得分的平方
    A_squared = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            # 计算点积
            dot_product = np.dot(normalized[i], normalized[j])
            # 缩放并计算平方
            A_ij = dot_product / np.sqrt(d)
            A_squared[i][j] = A_ij ** 2
    
    # 步骤3：贪心选择，最大化全局注意力信息总量S
    S = 0.0
    for j in range(1, n):
        # 收集位置j的所有前置位置的注意力得分平方
        scores = []
        for i in range(j):
            scores.append(A_squared[i][j])
        
        # 降序排序，选择最大的c_j个
        scores.sort(reverse=True)
        S += sum(scores[:capacities[j]])
    
    # 步骤4：输出整数化得分
    return round(100 * S)

if __name__ == "__main__":
    # 读取n和d
    n, d = map(int, input().split())
    
    # 读取特征向量
    vectors = []
    for _ in range(n):
        vec = list(map(float, input().split()))
        vectors.append(vec)
    
    # 读取计算容量
    capacities = list(map(int, input().split()))
    
    # 计算并输出结果
    result = solve(n, d, vectors, capacities)
    print(result)

Java

import java.util.*;

public class Main {
    public static int solve(int n, int d, double[][] vectors, int[] capacities) {
        // 步骤1：对所有特征向量进行RMSNorm归一化
        double[][] normalized = new double[n][d];
        for (int i = 0; i < n; i++) {
            // 计算均方根值
            double sumSquare = 0.0;
            for (int k = 0; k < d; k++) {
                sumSquare += vectors[i][k] * vectors[i][k];
            }
            double rms = Math.sqrt(sumSquare / d);
            // 归一化
            for (int k = 0; k < d; k++) {
                normalized[i][k] = vectors[i][k] / rms;
            }
        }
        
        // 步骤2：计算注意力得分的平方
        double[][] ASquared = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算点积
                double dotProduct = 0.0;
                for (int k = 0; k < d; k++) {
                    dotProduct += normalized[i][k] * normalized[j][k];
                }
                // 缩放并计算平方
                double Aij = dotProduct / Math.sqrt(d);
                ASquared[i][j] = Aij * Aij;
            }
        }
        
        // 步骤3：贪心选择，最大化全局注意力信息总量S
        double S = 0.0;
        for (int j = 1; j < n; j++) {
            // 收集位置j的所有前置位置的注意力得分平方
            List<Double> scores = new ArrayList<>();
            for (int i = 0; i < j; i++) {
                scores.add(ASquared[i][j]);
            }
            
            // 降序排序，选择最大的c_j个
            Collections.sort(scores, Collections.reverseOrder());
            for (int i = 0; i < Math.min(capacities[j], scores.size()); i++) {
                S += scores.get(i);
            }
        }
        
        // 步骤4：输出整数化得分
        return (int) Math.round(100 * S);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取n和d
        int n = sc.nextInt();
        int d = sc.nextInt();
        
        // 读取特征向量
        double[][] vectors = new double[n][d];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                vectors[i][j] = sc.nextDouble();
            }
        }
        
        // 读取计算容量
        int[] capacities = new int[n];
        for (int i = 0; i < n; i++) {
            capacities[i] = sc.nextInt();
        }
        
        // 计算并输出结果
        int result = solve(n, d, vectors, capacities);
        System.out.println(result);
        
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int solve(int n, int d, vector<vector<double>>& vectors, vector<int>& capacities) {
    // 步骤1：对所有特征向量进行RMSNorm归一化
    vector<vector<double>> normalized(n, vector<double>(d));
    for (int i = 0; i < n; i++) {
        // 计算均方根值
        double sumSquare = 0.0;
        for (int k = 0; k < d; k++) {
            sumSquare += vectors[i][k] * vectors[i][k];
        }
        double rms = sqrt(sumSquare / d);
        // 归一化
        for (int k = 0; k < d; k++) {
            normalized[i][k] = vectors[i][k] / rms;
        }
    }
    
    // 步骤2：计算注意力得分的平方
    vector<vector<double>> ASquared(n, vector<double>(n, 0.0));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 计算点积
            double dotProduct = 0.0;
            for (int k = 0; k < d; k++) {
                dotProduct += normalized[i][k] * normalized[j][k];
            }
            // 缩放并计算平方
            double Aij = dotProduct / sqrt(d);
            ASquared[i][j] = Aij * Aij;
        }
    }
    
    // 步骤3：贪心选择，最大化全局注意力信息总量S
    double S = 0.0;
    for (int j = 1; j < n; j++) {
        // 收集位置j的所有前置位置的注意力得分平方
        vector<double> scores;
        for (int i = 0; i < j; i++) {
            scores.push_back(ASquared[i][j]);
        }
        
        // 降序排序，选择最大的c_j个
        sort(scores.begin(), scores.end(), greater<double>());
        int limit = min(capacities[j], (int)scores.size());
        for (int i = 0; i < limit; i++) {
            S += scores[i];
        }
    }
    
    // 步骤4：输出整数化得分
    return (int)round(100 * S);
}

int main() {
    // 读取n和d
    int n, d;
    cin >> n >> d;
    
    // 读取特征向量
    vector<vector<double>> vectors(n, vector<double>(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> vectors[i][j];
        }
    }
    
    // 读取计算容量
    vector<int> capacities(n);
    for (int i = 0; i < n; i++) {
        cin >> capacities[i];
    }
    
    // 计算并输出结果
    int result = solve(n, d, vectors, capacities);
    cout << result << endl;
    
    return 0;
}

题目内容

你正在设计一种跨模态知的大模型精准度机制，给定一个长度为 $n$ 的输入 $token$ 序列，每个位置 $j$ 拥有一个 $d$维特征向量 $X_j \in \mathbb{R}^d$和一个正整数计算容量 $c_j$，表示该位置最多可接收来自前 $j$ 位置的信息连接数。

系统需完成以下步骤：

1. $RMSNorm$ 归一化：对所有特征向量进行 $RMSNorm$ 归一化本题取$(\gamma = 1, \epsilon = 0)$：

   每个特征向量记为$x_i \in \mathbb{R}^d$，其第 $k$ 个分量为 $x_i[k]$。$RMSNorm$ 定义为：

   $\hat{X_i} = \frac{ x_i}{\sqrt{\frac{1}{d}\sum_{k=1}^{d}x_i[k]^2 + \epsilon}}\cdot\gamma$

2. 注意力得分计算：计算每对位置 $i<j$ 的注意力得分，使用标准缩放点积公式（基于 $RMSNorm$ 归一化向量）：

   $A_{ij} = \frac{\hat{x_i} \cdot \hat{x_j}}{\sqrt{d}}$

3. 掩码矩阵构造：构造下三角注意力掩码矩阵$M \in \{0,1\}^{n \times n}$，满足入度约束：

   $\forall j \in [0, n), \sum_{i=0}^{j-1} M_{ij} \leq c_j$

4. 目标函数最大化：最大化全局注意力信息总量，全局注意力信息总量定义为所有激活连接的平方注意力得分之和：

   $S = \sum_{j=0}^{n-1} \sum_{i=0}^{j-1} M_{ij} \cdot A_{ij}^2$

5. 输出整数化得分：最终返回将最大化 $S$ 乘以 $100$ 后四舍五入得到的整数，以实现保留两位小数精度的整数化表示：

   $\text{round}(100 \cdot S)$

输入描述

• 第 $1$ 行: $n$ $d$，以空格分隔，分别表示 $token$ 序列长度和向量维度。
• 接下来 $n$ 行：每行 $d$ 个浮点数，以空格分隔，表示 $x_j$。
• 最后 $1$ 行: $n$ 个正整数，以空格分隔，表示 $c_j$。

约束条件

• $1 \leq n \leq 1000$
• $1 \leq d \leq 100$
• 所有向量非零

输出描述

返回一个整数，即上述步骤 $5$ 的整数化得分

样例1

输入

4 2
2.0 2.0
3.0 0.0
0.0 4.0
1.0 1.0
1 2 1 3

输出

600

说明

位置 $0$：$RMSNorm$ 归一化为 $[1, 1]$；无前置位置$→$对信息总量贡献 $0$

位置 $1$：$RMSNorm$ 归一化为 $[\sqrt{2}, 0]$；前置位置 $j=0$，$A_{01}^2 = 1；c_1 = 2$，选择接收来自 $j=0$ 的信息$→$对信息总量贡献 $1$

位置 $2：RMSNorm$ 归一化为 $[0, \sqrt{2}]$；前置位置 $j=0$ 和 $j=1$，计算 $A_{02}^2=1$,$A_{12}^2 = 0$；$c_2 = 1$，选择接收来自 $j=0$ 的信息$→$对信息总量贡献 $1$

位置 $3：RMSNorm$ 归一化为 $[1, 1]$；前置位置 $j=0$ 和 $j=1$ 和 $j=2$，计算 $A_{03}^2 = 2$，$A_{13}^2 = 1$，$A_{23}^2 = 1$；$c_2 = 3$，选择接收来自 $j=0$ 和 $j=1$ 和 $j=2$ 的信息$→$对信息总量贡献 $4$

最大化 $S=6$，输出整数化得分 $600$

样例2

输入

3 2
1.0 0.0
0.0 1.0
1.0 1.0
1 1 2

输出

200

说明

位置 $0：RMSNorm$ 归一化为 $[\sqrt{2}, 0]$；无前置位置$→$对信息总量贡献 $0$

位置 $1：RMSNorm$ 归一化为 $[0, \sqrt{2}]$；前置位置 $j=0$，$A_{01}^2 = 0$；$c_1 = 1$，选择接收来自 $i=0$ 的信息$→$对信息总量贡献 $0$

位置 $2：RMSNorm$ 归一化为 $[1, 1]$；前置位置 $j=0$ 和 $j=1$，计算 $A_{02}^2 = 1$，$A_{12}^2 = 1$；$c_2 = 2$，选择接收来自 $j=0$ 和 $j=1$ 的信息$→$对信息总量贡献 $2$

最大化 $S=2$，输出整数化得分 $200$